Biplanar graphs: A survey
A biplanar graph is the union of two planar graphs; thus its thickness is at most two. In this survey article, the author presents various properties of biplanar graphs, two special families of biplanar graphs (doubly linear graphs and rectangle visibility graphs), and extensions to other surfaces, both orientable and nonorientable (biembeddings). \textit{A. Mansfield} [Math. Proc. Camb. Philos. Soc. 93, 9-23 (1983; Zbl 0503.68048)] showed that determining whether a given graph is biplanar is an NP-complete problem. However, as shown in the present paper, every graph is homeomorphic to a biplanar graph.
- Geometric thickness in a grid
- Note on \(k\)-planar crossing numbers
- The biplanar tree graph
- Geometric biplane graphs. I: Maximal graphs
- Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
- Planarization and fragmentability of some classes of graphs
- Finding a biplanar imbedding of C_n C_n C_l P_m.
- Empires Make Cartography Hard: The Complexity of the Empire Colouring Problem
- scientific article; zbMATH DE number 3845604 (Why is no real title available?)
- Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method
- The complexity of the empire colouring problem
- Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
- On the bigenus of the complete graphs
- On the complexity of the maximum biplanar subgraph problem
- Index 3 biembeddings of the complete graphs
- On the Biplanarity of Blowups
- On the biplanarity of blowups
- The thickness of some complete bipartite and tripartite graphs
- A note on Halton's conjecture
- Planar-toroidal decomposition of \(K_{12}\)
- Remarks on the thickness and outerthickness of a graph
This page was built for publication: Biplanar graphs: A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1388965)
