On rectangular cartograms

A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good rectangular cartograms are hard to generate: The area specifications for each rectangle may make it impossible to realize correct adjacencies between the regions and so hamper the intuitive understanding of the map.

We present the first algorithms for rectangular cartogram construction. Our algorithms depend on a precise formalization of region adjacencies and build upon existing VLSI layout algorithms. Furthermore, we characterize a non-trivial class of rectangular subdivisions for which exact cartograms can be computed efficiently. An implementation of our algorithms and various tests show that in practice, visually pleasing rectangular cartograms with small cartographic error can be generated effectively.     

Location of rectilinear center trajectories

A rectilinear center trajectory is a polygonal line consisting only of horizontal and vertical segments which minimizes the maximum distance tom given points in the plane. In this paper a polynomial time geometric procedure, to find a center trajectory subject to the number of bends, is presented. When the polygonal is constrained on the extreme segments a modified algorithm is designed.     

Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.     

On the eigenvalues and eigenvectors of certain finite,vertex-weighted,bipartite graphs

The established, spectral characterisation of bipartite graphs with unweighted vertices (which are here termed homogeneous graphs) is extended to those bipartite graphs (called heterogeneous) in which all of the vertices in one set are weighted h₁ , and each of those in the other set of the bigraph is weighted h₂. All the eigenvalues of a homogeneous bipartite graph occur in pairs, around zero, while some of the eigenvalues of an arbitrary, heterogeneous graph are paired around $\text{1}\text{2}$(h₁ + h₂), the remainder having the value h₂ (or h_l). The well-documented, explicit relations between the eigenvectors belonging to “paired” eigenvalues of homogeneous graphs are extended to relate the components of the eigenvectors associated with each couple of “paired” eigenvalues of the corresponding heterogeneous graph. Details are also given of the relationships between the eigenvectors of an arbitrary, homogeneous, bipartite graph and those of its heterogeneous analogue.     

On topological diversity of rectilinear representations of countably infinite graphs

We prove that, for each simple graph G whose set of vertices is countably infinite, there is a family ${\varvec{\mathcal{R}}(\varvec{G})}$ of the cardinality of the continuum of graphs such that (1) each graph ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ is isomorphic to G, all vertices of H are points of the Euclidean space E ³, all edges of H are straight line segments (the ends of each edge are the vertices joined by it), the intersection of any two edges of H is either their common vertex or empty, and any isolated vertex of H does not belong to any edge of H; (2) all sets ${\varvec{\mathcal{B}}(\varvec{H})}$ ( ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ ), where ${\varvec{\mathcal{B}}(\varvec{H})\subset \mathbf{E}^3}$ is the union of all vertices and all edges of H, are pairwise not homeomorphic; moreover, for any graphs ${\varvec{H}_1 \in \varvec{\mathcal{R}}(\varvec{G})}$ and ${\varvec{H}_2 \in \varvec{\mathcal{R}}(\varvec{G})}$ , ${\varvec{H}_1 \ne \varvec{H}_2}$ , and for any finite subsets ${\varvec{S}_i \subset \varvec{\mathcal{B}}(\varvec{H}_i)}$ (i = 1, 2), the sets ${\varvec{\mathcal{B}}(\varvec{H}_1){\setminus} \varvec{S}_1}$ and ${\varvec{\mathcal{B}}(\varvec{H}_2){\setminus} \varvec{S}_2}$ are not homeomorphic.     

On graphs preserving rectilinear shortest paths in the presence of obstacles

In physical VLSI design, network design (wiring) is the most time-consuming phase. For solving global wiring problems, we propose to first compute from the layout geometry a graph that preserves all shortest paths between pairs of relevant points, and then to operate on that graph for computing shortest paths, Steiner minimal tree approximations, or the like. For a set of points and a set of simple orthogonal polygons as obstacles in the plane, withn input points (polygon corner or other) altogether, we show how a shortest paths preserving graph of sizeO(n logn) can be computed in timeO(n logn) in the worst case, with spaceO(n). We illustrate the merits of this approach with a simple example: If the length of a longest edge in the graph is bounded by a polynomial inn, an assumption that is clearly fulfilled for graphs derived from VLSI layout geometries, then a shortest path can be computed in timeO(n logn log logn) in the worst case; this result improves on the known best one ofO(n(logn)^3/2).     

On 3-choosability of triangle-free plane graphs

It is known that every triangle-free plane graph is 3-colorable.However,such a triangle-free plane graph may not be 3-choosable.In this paper,we prove that a triangle-free plane graph is 3-choosable if no 4-cycle in it is adjacent to a 4-or a 5-cycle.This improves some known results in this direction.     

On the edge-binding number of some plane graphs

1. IntroductionSince WOodall gave out the concept of biIldi11g Ilu1lJber in 1973[l] ! the bil1ding nunlber fOrsome specia1 classes have beeIl studied by Kane and WaIlg Jianfang[']. Mirolawa Skowronskahave studied the binding number of Halin-graph[']. ZI1ang Zhongfu, Liu Li1lzhong andZhang Jianxun have extended the bil1di11g nuInber to the edges and studied tlle edge-bindingnumber of path, cycle, coInplete grapl1. I1l this paper, we study the edge-binding number ofouter plane graph, Ha…     

Boolean approaches to graph embeddings related to VLSI

This paper discusses the development of Boolean methods in some topics on graph embeddings which are related to VLSI. They are mainly the general theory of graph embeddability, the orientabilities of a graph and the rectilinear layout of an electronic circuit.     

A vertex-face assignment for plane graphs

For every planar straight line graph (Pslg), there is a vertex-face assignment such that every vertex is assigned to at most two incident faces, and every face is assigned to all its reflex corners and one more incident vertex. Such an assignment allows us to augment every disconnected Pslg into a connected Pslg such that the degree of every vertex increases by at most two.     

On the facial Thue choice index of plane graphs

Let $G$ be a plane graph, and let $\phi$ be a colouring of its edges. The edge colouring $\phi$ of $G$ is called facial non-repetitive if for no sequence $r_1,r_2,\dots ,r_{2n}$, $n\ge 1$, of consecutive edge colours of any facial path we have $r_i=r_{n+i}$ for all $i=1,2,\dots ,n$. Assume that each edge $e$ of a plane graph $G$ is endowed with a list $L\left(e\right)$ of colours, one of which has to be chosen to colour $e$. The smallest integer $k$ such that for every list assignment with minimum list length at least $k$ there exists a facial non-repetitive edge colouring of $G$ with colours from the associated lists is the facial Thue choice index of $G$, and it is denoted by ${\pi }_{fl}\left(G\right)$. In this article we show that ${\pi }_{fl}^{\prime }\left(G\right)\le 291$ for arbitrary plane graphs $G$. Moreover, we give some better bounds for special classes of plane graphs.     

The coupled thermoelastic problem for a plane with a rectilinear crack

We solve the thermoelastic problem for a plane with a rectilinear heat-conducting crack whose conductivity depends on its opening. By modeling the crack as a thin inclusion of variable thickness we reduce the problem to a system of singular integrodifferential equations for the potential densities of the temperature field. We study the behavior of the unknown functions at the ends of the contour of integration and, using a numerical-iteration method, we also determine the solution of the problem. We find an approximate asymptotic solution in the case of a weakly conducting crack.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 31, 1990, pp. 54–58.     

A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

Characterizations of bipartite and Eulerian partial duals of ribbon graphs

Huggett and Moffatt characterized all bipartite partial duals of a plane graph in terms of all-crossing directions of its medial graph. Then Metsidik and Jin characterized all Eulerian partial duals of a plane graph in terms of semi-crossing directions of its medial graph. Plane graphs are ribbon graphs with genus 0. In this paper, by introducing the notion of modified medial graphs and using their all-crossing directions, we first extend Huggett and Moffatt’s result from plane graphs to ribbon graphs. Then we characterize all Eulerian partial duals of any ribbon graph in terms of crossing-total directions of its medial graph, which are simpler than semi-crossing directions.     

Cubic irreducible graphs for the projective plane

A characterization of all cubic finite graphs that do not embed in the real projective plane P is given in the sense that Kuratowski characterized all non-planar finite graphs. Specifically it is shown that there exist exactly 6 cubic irreducible graphs for P.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

Entire colouring of plane graphs

It was conjectured by Kronk and Mitchem in 1973 that simple plane graphs of maximum degree Δ are entirely (Δ+4)-colourable, i.e., the vertices, edges, and faces of a simple plane graph may be simultaneously coloured with Δ+4 colours in such a way that adjacent or incident elements are coloured by distinct colours. Before this paper, the conjecture has been confirmed for Δ?3 and Δ?6 (the proof for the Δ=6 case has a correctable error). In this paper, we settle the whole conjecture in the positive. We prove that if G is a plane graph with maximum degree 4 (parallel edges allowed), then G is entirely 8-colourable. If G is a plane graph with maximum degree 5 (parallel edges allowed), then G is entirely 9-colourable.