We prove that a graph $G$ is quasi-planar - i.e. quasi-isometric to a planar graph - if and only if it can be obtained by iterating the following two operations a bounded number of times: a) subdividing each edge into a path of bounded length, and b) taking the intersection graph of a family of connected subgraphs covering $G$. This applies both to infinite graphs, and to families of finite graphs with uniform constants. The backward implication relies on, and generalises, a deep result of Davies, partly proved independently by Chang, Conroy, Tan&Zheng, saying that every string graph is quasi-planar. The forward implication requires new ideas. As a byproduct of our proofs, we deduce that every contraction minor of a quasi-planar graph is quasi-planar. Moreover, if $G$ admits a tree-decomposition with adhesions of bounded diameter and quasi-planar induced bags, then $G$ is itself quasi-planar. Our results apply to other graph classes as well, and we offer various tools for understanding quasi-isometries as well as bi-Lipschitz equivalences between graphs.
A quasi-tree of a connected ribbon graph is a spanning ribbon subgraph with exactly one boundary component; quasi-trees play the role of spanning trees in the topological graph theory of embedded graphs. We prove that counting them is #P-complete under polynomial-time Turing reductions, already for bouquets. The proof...
In this article, we introduce the notion of connected finite graphs with disjoint cycles in normal form and show that any such graph can be transformed into a normal form graph via a finite sequence of in-splittings and out-splittings. Consequently, we provide number-theoretic criteria for meteor graphs of length three...
A finite simple graph $G$ is called a cograph if it does not contain the path on four vertices $P_4$ as an induced subgraph. It is classically known that the family of cographs are well-quasi-ordered by the induced subgraph relation \cite{D}. In preceding work of Knudsen and the third author \cite[Theorem 7.2]{KR}, it...
Adityo Mamun, Jonathan Nalikka, Eric Ramos· 0 citations
We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of M\"utze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by...
For a fixed graph F, the F-degree of a vertex v in a host graph H is the number of subgraphs of H isomorphic to F that contain v, and H is F-irregular if its F-degrees are pairwise distinct. We show that every finite connected graph F on at least three vertices admits a finite connected F-irregular host. For noncomplet...
We prove three theorems on the flow monoids of finite graphs. First, we show that a non-empty finite graph G = (V, E) is connected if and only if its flow monoid contains a constant map on V, equivalently, if and only if it contains all constant maps on V. Second, we give a new characterization of graph minors in terms...
A. Assem, H. Derets, C. Nehaniv· Electronic Proceedings in Th...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
