Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid

DOI10.1007/978-3-642-25870-1_29MaRDI QIDQ3104787zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Elad Cohen, Juraj Stacho

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

chordal \(B _{0}\)-VPG graphspolynomial time algorithms

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Vertex intersection graphs of paths on a grid: characterization within block graphs
• Characterising chordal contact \(B_0\)-VPG graphs
• Vertex Intersection Graphs of Paths on a Grid
• On some special classes of contact \(B_0\)-VPG graphs
• String graphs of k-bend paths on a grid

Cites work

• Algorithmic graph theory and perfect graphs
• Connectivity threshold for random chordal graphs
• Constant tolerance intersection graphs of subtrees of a tree
• Drawing Graphs on Two and Three Lines
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 219230 (Why is no real title available?)
• scientific article; zbMATH DE number 4185548 (Why is no real title available?)
• Incidence matrices and interval graphs
• Intersection graphs of segments
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• String graphs of k-bend paths on a grid
• String graphs. II: Recognizing string graphs is NP-hard
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Testing simultaneous planarity when the common graph is 2-connected
• Topology of Thin Film RC Circuits
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(21)

• Characterising chordal contact \(B_0\)-VPG graphs
• On contact graphs of paths on a grid
• On some special classes of contact \(B_0\)-VPG graphs
• Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
• On computing the number of (BC-)subtrees, eccentric subtree number, and global and local means of trees
• Characterising circular-arc contact \(B_0\)-VPG graphs
• Multi-distance granularity structural \(\alpha \)-subtree index of generalized Bethe trees
• Bounds on the bend number of split and cocomparability graphs
• Enumeration of BC-subtrees of trees
• 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
• On algorithms for enumerating BC-subtrees of unicyclic and edge-disjoint bicyclic graphs
• Maximum independent set on \(B_1\)-VPG graphs
• Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
• On spiro and polyphenyl hexagonal chains with respect to the number of BC-subtrees
• On rectangle intersection graphs with stab number at most two
• Posets and VPG graphs
• \(B_0\)-VPG representation of AT-free outerplanar graphs
• B0-VPG Representation of AT-free Outerplanar Graphs
• Constant time enumeration of weighted trees
• Characterizations of cographs as intersection graphs of paths on a grid

This page was built for publication: Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104787)