Narrow Results

Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height , which can be constructed in linear time. This improves the best previous bound of .

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem.

1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2. Each embedding of a closed convex curve has dilation ≥ 1.00157.

3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation .

We prove that computing a geometric minimum-dilation graph on a given set of points in the plane, using not more than a given number of edges, is an NP-hard problem, no matter if edge crossings are allowed or forbidden. We also show that the problem remains NP-hard even when a minimum-dilation tour or path is sought; not even an FPTAS exists in this case.

This paper is an exploration of simple four-regular graphs in the plane (i.e. loop-free and with no more than one edge between any two nodes). Such graphs are fundamental to the theory of knots and links in three dimensional space, and their planar diagrams. We dedicate this paper to Frank Harary (1921–2005), whose fascination with graphs of knots inspired this work, and with whom we had the pleasure of developing this paper.

We introduce a polynomial for plane graphs, which is proposed to equal the Dubrovnik polynomial of the corresponding alternating link diagrams via the medial construction. Then using this polynomial we define another polynomial for doubly edge-weighted plane graphs, which has a natural connection with Dubrovnik polynomial of links formed from plane graphs by edge-tangle replacements. In the final, via this connection we give an explanation for a result due to Lipson and compute the Dubrovnik polynomials of classical pretzel links.

In this paper, we associate a plane graph G with an oriented link by replacing each vertex of G with a special oriented n-tangle diagram. It is shown that such an oriented link has the minimum genus over all orientations of its unoriented version if its associated plane graph G is 2-connected. As a result, the genera of a large family of unoriented links are determined by an explicit formula in terms of their component numbers and the degree sum of their associated plane graphs.

This paper extends and updates the survey [J. Czap, S. Jendrol’, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703] on facial colorings. Different types of colorings of plane graphs are discussed in their vertex, edge, total, and list versions.

Irreducible triangulations are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Fusy proposed a straight-line grid drawing algorithm for irreducible triangulations, whose grid size is asymptotically with high probability 11n/27 × 11n/27 up to an additive error of . Later on, Fusy generalized the idea to quadrangulations and obtained a straight-line grid drawing, whose grid size is asymptotically with high probability 13n/27 × 13n/27 up to an additive error of . In this paper, we first prove that the above two straight-line grid drawing algorithms for irreducible triangulations and quadrangulations actually produce open rectangle-of-influence drawings for them respectively. Therefore, the above mentioned straight-line grid drawing size bounds also hold for the open rectangle-of-influence drawings. These results improve previous known drawing sizes.

In the second part of the paper, we present another application of the results obtained by Fusy. We present a linear time algorithm for constructing a rectangular dual for a randomly generated irreducible triangulation with n vertices, one of its dimensions equals asymptotically with high probability, up to an additive error of . In addition, we prove that the one dimension tight bound for a rectangular dual of any irreducible triangulations with n vertices is (n + 1)/2.

In [1], Borodin et al. figured out a gap of [5], and gave a new proof with the similar technique. The purpose of this note is to fix the gap of [5] by slightly revising the definition of special faces, and adding a few lines of explanation in the original proofs of [5] (new added text are all in italic type).

The equitable chromatic number χ_e(G) of a graph G is the smallest integer k for which G has a proper k-coloring such that the number of vertices in any two color classes differ by at most one. In 1973, Meyer conjectured that the equitable chromatic number of a connected graph G, which is neither a complete graph nor an odd cycle, is at most Δ(G). We prove that this conjecture holds for 2-degenerate graphs with Δ(G) ≥ 5 and plane graphs without 3, 4 and 5 cycles.

In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph G has a convex drawing if and only if G is internally triconnected. It has been known that an internally triconnected plane graph G of n vertices has a convex grid drawing on a grid of O(n³) area if the triconnected component decomposition tree of G has at most four leaves. In this paper, we improve the area bound O(n³) to O(n²), which is optimal up to a constant factor. More precisely, we show that G has a convex grid drawing on a 2n × 4n grid. We also present an algorithm to find such a drawing in linear time.

In the point-set embeddability problem, we are given a plane graph G with n vertices and a point set S with the same number of points. Now the goal is to answer the question whether there exists a straight-line drawing of G such that each vertex is represented as a distinct point of S as well as to provide an embedding if one does exist. This problem has recently been solved in O(n²log n) time for plane 3-trees. In this paper, we present a new efficient algorithm with time complexity O(n^4/3+ϵlog n). We also present an O(nk⁴) time algorithm for the case when |S| = k > n. This is a significant improvement over the best algorithm for this case in the literature, which runs in O(nk⁸) time.

A plane graph G is entirely k-choosable if, for every list L of colors satisfying L(x) = k for x ∈ V(G) ∪ E(G) ∪ F(G), there exists a coloring which assigns to each vertex, each edge and each face a color from its list so that any adjacent or incident elements receive different colors. In this paper, we show that every plane graph G with maximum degree Δ ≤ 5 is entirely (Δ + 5)-choosable.

A graph $G$ is $k$-choosable if it has an $L$-coloring whenever $L$ is a list assignment such that $|L(v)|\ge k$ for all $v\in V(G)$. We provide two sufficient conditions for 3-choosability of plane graphs. Every plane graph with $d^{\nabla }\ge 2$ without cycles of length from 4 to 6 and special 7-cycles is 3-choosable. Every plane graph with $d^{\nabla }\ge 3$ without cycles of length from 4 to 5 and adjacent 6-cycles is also 3-choosable.

A random geometric graph, $G(n,r)$, is formed by choosing $n$ points independently and uniformly at random in a unit square; two points are connected by a straight-line edge if they are at Euclidean distance at most $r$. For a given constant $k$, we show that $n^{\frac{-k}{2k-2}}$ is a distance threshold function for $G(n,r)$ to have a connected subgraph on $k$ points. Based on this, we show that $n^{-2/3}$ is a distance threshold for $G(n,r)$ to be plane, and $n^{-5/8}$ is a distance threshold to be planar. We also investigate distance thresholds for $G(n,r)$ to have a non-crossing edge, a clique of a given size, and an independent set of a given size.

Let $G$ be a plane graph with a set of faces $F(G)$ and $\psi :V(G)\to \{1,2,\dots ,k\}$ be a (not necessarily proper) vertex $k$-coloring. $\psi$ is called polychromatic if all $k$ colors appear on the vertices of its boundary for each face (also the outer-face) $f\in F(G)$. The polychromatic number of $G$ is the largest number of colors $k$ such that $G$ admits a polychromatic $k$-coloring. In the paper, we consider a class of plane graphs ${𝒢}$ with minimum face size $g$, in each of which every pair of faces have at most $t$ common incident vertices, and show that the polychromatic number for each $G\in {𝒢}$ is at least $g-t-2$. When $g\ge 4t+4$, the result improves a known lower bound.

Let $G$ be a finite undirected simple connected graph with vertex set $V(G)$ and edge set $E(G)$. A vertex $u\in V(G)$ resolves two elements (vertices or edges) $v,w\in V(G)\cup E(G)$ if $d(u,v)\ne d(u,w)$. A subset $S_m$ of vertices in $G$ is called a mixed metric generator for $G$ if every two distinct elements (vertices and edges) of $G$ are resolved by some vertices of $S_m$. The minimum cardinality of a mixed metric generator for $G$ is called the mixed metric dimension and is denoted by ${dim}_m(G)$. In this paper, we study the mixed metric dimension for the plane graph of web graph ${𝕎}_n$ and convex polytope ${𝔻}_n$.

We connect two aspects of graph drawing, namely angular resolution, and the possibility to draw with all angles an integer multiple of 2π/d. A planar graph with angular resolution at least π/2 can be drawn with all angles an integer multiple of π/2 (rectilinear). For d ≠ 4, d > 2, an angular resolution of 2π/d does not imply that the graph can be drawn with all angles an integer multiple of 2π/d. We argue that the exceptional situation for d = 4 is due to the absence of triangles in the rectangular grid.

The virtual-height (virtual-width) of a straight line embedding of a plane graph in the xy-plane is the number of vertices with pairwise distinct y-coordinates (x-coordinates). We show that any plane graph of order n has a straight line embedding of virtual-height at most and virtual-width at most and present a polynomial time algorithm which obtains such an embedding.