Grid intersection graphs and order dimension

DOI10.1007/S11083-017-9437-0MaRDI QIDQ722596zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Stefan Felsner, Udo Hoffmann, Veit Wiechert

Publication date 27 July 2018

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02482

zbMATH Keywords

order dimensiongrid intersection graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)

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.

Recommendations

• Ferrers dimension of grid intersection graphs
• Intersection dimension of bipartite graphs
• Intersection dimensions of graph classes
• Grid intersection graphs and boxicity
• Interval dimension is a comparability invariant

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• A unified approach to visibility representations of planar graphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Exploiting air-pressure to map floorplans on point sets
• Independent and hitting sets of rectangles intersecting a diagonal line
• Intersection dimension of bipartite graphs
• Jump number of two-directional orthogonal ray graphs
• Max point-tolerance graphs
• On orthogonal ray graphs
• On the Ferrers dimension of a digraph
• On the number of rectangulations of a planar point set
• On the order dimension of outerplanar maps
• Orthogonal segment stabbing
• Partially Ordered Sets
• Planar graphs and poset dimension
• Posets and planar graphs
• The Dimension of a Comparability Graph
• The clique problem in ray intersection graphs
• The complexity of the partial order dimension problem: closing the gap
• The order dimension of planar maps revisited
• Topology of Thin Film RC Circuits
• \(p\)-box: a new graph model

Cited in

(16)

• Embedding linear orders in grids
• Forced pairs in \(A\)-Stick graphs
• Ferrers dimension of grid intersection graphs
• Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
• Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
• Recognizing geometric intersection graphs stabbed by a line
• Intersection graphs of rays and grounded segments
• Refining the hierarchies of classes of geometric intersection graphs
• Colored anchored visibility representations in 2D and 3D space
• Twin-width IV: ordered graphs and matrices
• Recognizing stick graphs with and without length constraints
• Stick graphs with length constraints
• Intersection dimension of bipartite graphs
• On grid intersection graphs
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Separability, boxicity, and partial orders

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)