Grid intersection graphs and order dimension
From MaRDI portal
Publication:722596
DOI10.1007/S11083-017-9437-0zbMATH Open1404.05178arXiv1512.02482OpenAlexW2963296039MaRDI QIDQ722596FDOQ722596
Authors: Steven Chaplick, Stefan Felsner, Udo Hoffmann, Veit Wiechert 
Publication date: 27 July 2018
Published in: Order (Search for Journal in Brave)
Abstract: We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.
Full work available at URL: https://arxiv.org/abs/1512.02482
Recommendations
Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)
Cites Work
- Planar graphs and poset dimension
- The clique problem in ray intersection graphs
- Partially Ordered Sets
- On orthogonal ray graphs
- A unified approach to visibility representations of planar graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Orthogonal segment stabbing
- On the Ferrers dimension of a digraph
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- On the number of rectangulations of a planar point set
- Max point-tolerance graphs
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
- Independent and hitting sets of rectangles intersecting a diagonal line
- Jump number of two-directional orthogonal ray graphs
- Topology of Thin Film RC Circuits
- Posets and planar graphs
- On the order dimension of outerplanar maps
- The order dimension of planar maps revisited
- The complexity of the partial order dimension problem: closing the gap
- The Dimension of a Comparability Graph
- \(p\)-box: a new graph model
- Intersection dimension of bipartite graphs
- Exploiting air-pressure to map floorplans on point sets
Cited In (16)
- Embedding linear orders in grids
- Forced pairs in \(A\)-Stick graphs
- Stick graphs with length constraints
- Recognizing stick graphs with and without length constraints
- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
- Separability, boxicity, and partial orders
- Intersection dimension of bipartite graphs
- Recognizing geometric intersection graphs stabbed by a line
- Twin-width IV: ordered graphs and matrices
- Ferrers dimension of grid intersection graphs
- Intersection graphs of rays and grounded segments
- On grid intersection graphs
- On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
- Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
- Refining the hierarchies of classes of geometric intersection graphs
- Colored anchored visibility representations in 2D and 3D space
This page was built for publication: Grid intersection graphs and order dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722596)
