73 citations · 178 across the 49 of their papers we have counts for
9 papers · 1 filter
Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs
Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt
We study the recognition complexity of subgraphs of k-connected planar cubic graphs for k = 1, 2, 3. We present polynomial-time algorithms to recognize subgraphs of 1- and 2-connec…
On Comparable Box Dimension
Zdenek Dvorák, Daniel Goncalves, Abhiruk Lahiri +2
Two boxes in are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph is the minimum integer such…
Guarding Quadrangulations and Stacked Triangulations with Edges
Paul Jungeblut, Torsten Ueckerdt
Let be a plane graph. A face of is guarded by an edge if at least one vertex from is on the boundary of . For a planar graph class $\mat…
Planar graphs have bounded queue-number
Vida Dujmović, Gwenaël Joret, Piotr Micek +3
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called lay…
Beyond-Planarity: Density Results for Bipartite Graphs
Patrizio Angelini, Michael A. Bekos, Michael Kaufmann +2
Beyond-planarity focuses on the study of geometric and topological graphs that are in some sense nearly-planar. Here, planarity is relaxed by allowing edge crossings, but only with…
Pixel and Voxel Representations of Graphs
Muhammad Jawaherul Alam, Thomas Bläsius, Ignaz Rutter +2
We study contact representations for graphs, which we call pixel representations in 2D and voxel representations in 3D. Our representations are based on the unit square grid whose…