Grid intersection graphs and order dimension

DOI10.1007/s11083-017-9437-0zbMath1404.05178arXiv1512.02482OpenAlexW2963296039MaRDI QIDQ722596

Veit Wiechert, Udo Hoffmann, Stefan Felsner, Steven Chaplick

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

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

Related Items

Forced pairs in \(A\)-Stick graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Separability, boxicity, and partial orders ⋮ Recognizing geometric intersection graphs stabbed by a line ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ Stick graphs with length constraints ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Recognition and drawing of stick 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

Cites Work

• Max point-tolerance graphs
• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• The clique problem in ray intersection graphs
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• On orthogonal ray graphs
• On the order dimension of outerplanar maps
• Orthogonal segment stabbing
• A unified approach to visibility representations of planar graphs
• Planar graphs and poset dimension
• On the Ferrers dimension of a digraph
• A special planar satisfiability problem and a consequence of its NP- completeness
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• On the number of rectangulations of a planar point set
• The Order Dimension of Planar Maps Revisited
• The Complexity of the Partial Order Dimension Problem: Closing the Gap
• Jump Number of Two-Directional Orthogonal Ray Graphs
• The Dimension of a Comparability Graph
• (c-)AND: A new graph model
• Posets and planar graphs
• Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line
• Intersection Dimension of Bipartite Graphs
• Exploiting Air-Pressure to Map Floorplans on Point Sets
• Topology of Thin Film RC Circuits
• Partially Ordered Sets
• Boxicity and Poset Dimension