Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid

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

zbMATH Keywords

polynomial time algorithmschordal \(B _{0}\)-VPG graphs

Mathematics Subject Classification ID

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