Common-Face Embeddings of Planar Graphs
| dc.creator | Chen, Zhi-Zhong | |
| dc.creator | He, Xin | |
| dc.creator | Kao, Ming-Yang | |
| dc.date | 2001-02-10 | |
| dc.date.accessioned | 2026-07-07T03:16:55Z | |
| dc.date.available | 2026-07-07T03:16:55Z | |
| dc.description | Given a planar graph G and a sequence C_1,...,C_q, where each C_i is a family of vertex subsets of G, we wish to find a plane embedding of G, if any exists, such that for each i in {1,...,q}, there is a face F_i in the embedding whose boundary contains at least one vertex from each set in C_i. This problem has applications to the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let I be the input size, i.e., the total number of vertices and edges in G and the families C_i, counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in O(I log I) time for the special case where for each input family C_i, each set in C_i induces a connected subgraph of the input graph G. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints C_1,...,C_q only incurs a logarithmic factor of overhead. | |
| dc.description | A preliminary version appeared in the Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 195-204 | |
| dc.identifier | https://arxiv.org/abs/cs/0102007 | |
| dc.identifier | http://arxiv.org/abs/cs/0102007 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30537 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.2.2 | |
| dc.title | Common-Face Embeddings of Planar Graphs | |
| dc.type | text |