2011 | OriginalPaper | Buchkapitel
Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
verfasst von : Steven Chaplick, Elad Cohen, Juraj Stacho
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, known as
B
0
-VPG graphs. Recognizing these graphs is an NP-hard problem. In light of this, we focus on their subclasses. In the paper, we describe polynomial time algorithms for recognizing chordal
B
0
-VPG graphs, and for recognizing
B
0
-VPG graphs that have a representation on a grid with 2 rows.