Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
On-line convex planarity testing
Extended abstract
verfasst von : Giuseppe Di Battista, Roberto Tamassia, Luca Vismara
Erschienen in: Graph-Theoretic Concepts in Computer Science
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
An important class of planar straight-line drawings of graphs are convex drawings, where all faces are drawn as convex polygons. A graph is said to be convex planar if it admits a convex drawing. We consider the problem of testing convex planarity in a dynamic environment, where a graph is subject to on-line insertions of vertices and edges. We present on-line algorithms for convex planarity testing with the following performance, where n denotes the number of vertices of the graph: convex planarity testing and insertion of vertices take worst-case time O(1), insertion of edges takes amortized time O(log n), and the space requirement of the data structure is O(n). Furthermore, we give a new combinatorial characterization of convex planar graphs.