×

A dualizable representation for imbedded graphs. (English) Zbl 0841.05022

Alavi, Yousef (ed.) et al., Graph theory, combinatorics, and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988. New York: John Wiley & Sons Ltd. Wiley-Interscience Publication. 343-357 (1991).
Summary: A new representation is described for graphs imbedded in pseudomanifolds. The graphs may have loops and parallel edges, and they may be disconnected. It is shown that our representation has a well-defined dual that naturally extends the definition of surface duality. This representation is easily transformed to a data structure with a set of operators for modifying a graph, a set of query operators, and a set of navigation operators. Three variants of the data structure are described. For a graph with \(n\) vertices, the first provides \(O(1)\)-time updates and \(O(n)\)-time queries. The second provides \(O(n)\)-time updates and \(O(1)\)-time queries. The third, a tradeoff between the first two, provides \(O(\log n)\)-time updates and queries. The space used in all variants is linear in the size of the graph.
For the entire collection see [Zbl 0831.05002].

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite