On contact graphs of paths on a grid
From MaRDI portal
Publication:1725765
DOI10.1007/978-3-030-04414-5_22OpenAlexW2964212278MaRDI QIDQ1725765
Andrea Munaro, Zakir Deniz, Bernard Ries, Esther Galby
Publication date: 15 February 2019
Full work available at URL: https://arxiv.org/abs/1803.03468
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (5)
CPG graphs: some structural and hardness results ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Proper colorability of segment intersection graphs ⋮ On contact graphs of paths on a grid ⋮ On some special classes of contact \(B_0\)-VPG graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Intersection graphs of L-shapes and segments in the plane
- VPG and EPG bend-numbers of Halin graphs
- On the bend-number of planar and outerplanar graphs
- Characterizations of cographs as intersection graphs of paths on a grid
- Representations by contact and intersection of segments
- Some simplified NP-complete graph problems
- Classes and recognition of curve contact graphs
- The maximal clique and colourability of curve contact graphs
- On contact graphs of paths on a grid
- On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
- Vertex intersection graphs of paths on a grid: characterization within block graphs
- Minimal non-1-planar graphs
- On the Computational Complexity of Upward and Rectilinear Planarity Testing
- Graph Theory
- Equilateral L-Contact Graphs
- Vertex Contact Graphs of Paths on a Grid
- Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
- Vertex Intersection Graphs of Paths on a Grid
- Planar Graphs as VPG-Graphs
- Characterizations of derived graphs
- Combinatorial and Geometric Properties of Planar Laman Graphs
- Contact graphs of line segments are NP-complete
- Posets and VPG graphs
This page was built for publication: On contact graphs of paths on a grid
