Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
From MaRDI portal
Publication:3104787
DOI10.1007/978-3-642-25870-1_29zbMath1341.05171OpenAlexW1861204304MaRDI QIDQ3104787
Steven Chaplick, Juraj Stacho, Elad Cohen
Publication date: 16 December 2011
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_29
Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (18)
On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs ⋮ Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs ⋮ On computing the number of (BC-)subtrees, eccentric subtree number, and global and local means of trees ⋮ Vertex intersection graphs of paths on a grid: characterization within block graphs ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ On contact graphs of paths on a grid ⋮ On Spiro and polyphenyl hexagonal chains with respect to the number of BC-subtrees ⋮ Multi-distance granularity structural \(\alpha \)-subtree index of generalized Bethe trees ⋮ Posets and VPG graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ On rectangle intersection graphs with stab number at most two ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ Bounds on the bend number of split and cocomparability 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 ⋮ Enumeration of BC-subtrees of trees ⋮ On algorithms for enumerating BC-subtrees of unicyclic and edge-disjoint bicyclic graphs
Cites Work
- String graphs. II: Recognizing string graphs is NP-hard
- Connectivity threshold for random chordal graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Intersection graphs of segments
- Constant tolerance intersection graphs of subtrees of a tree
- Algorithmic graph theory and perfect graphs
- On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
- Incidence matrices and interval graphs
- String graphs of k-bend paths on a grid
- Testing Simultaneous Planarity When the Common Graph Is 2-Connected
- Vertex Intersection Graphs of Paths on a Grid
- Drawing Graphs on Two and Three Lines
- Topology of Thin Film RC Circuits
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
