1997 | ReviewPaper | Buchkapitel
On rectangle visibility graphs
verfasst von : Prosenjit Bose, Alice Dean, Joan Hutchinson, Thomas Shermer
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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 study the problem of drawing a graph in the plane so that the vertices of the graph are rectangles that are aligned with the axes, and the edges of the graph are horizontal or vertical lines-of-sight. Such a drawing is useful, for example, when the vertices of the graph contain information that we wish displayed on the drawing; it is natural to write this information inside the rectangle corresponding to the vertex. We call a graph that can be drawn in this fashion a rectangle-visibility graph, or RVG. Our goal is to find classes of graphs that are RVGs. We obtain several results:1.For 1 ≤ k ≤ 4, k-trees are RVGs.2.Any graph that can be decomposed into two caterpillar forests is an RVG.3.Any graph whose vertices of degree four or more form a distance-two independent set is an RVG.4.Any graph with maximum degree four is an RVG. Our proofs are constructive and yield linear-time layout algorithms.