### 1-bend 3-D orthogonal box-drawings: Two open problems solved.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph G is called elementary if G is connected and every edge belongs to a 1-factor of G. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face f of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of...

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.

It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48

Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.

In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.

We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.