Common-Face Embeddings of Planar Graphs

Title: Common-Face Embeddings of Planar Graphs

Abstract: This research focuses on a problem known as the Common-Face Embeddings of Planar Graphs (CFE). The CFE problem involves a planar graph and a sequence of vertex subsets, where each subset is associated with a specific family. The goal is to find a plane embedding of the graph that satisfies all the families, meaning that for each family, there is a face in the embedding that contains at least one vertex from each subset. The study investigates the complexity of this problem and presents an efficient algorithm for a special case where each subset induces a connected subgraph. The algorithm can find a plane embedding that satisfies the given families, if one exists, in O(IlogI) time. The CFE problem has applications in topological information recovery, geographical data, and VLSI design.

Main Research Question: How can we efficiently find a plane embedding of a graph that satisfies a given sequence of vertex subsets, especially when each subset induces a connected subgraph?

Methodology: The research uses graph theory and planar embedding techniques. It presents an algorithm that checks if a given planar graph satisfies a given sequence of vertex subsets. The algorithm is efficient for the special case where each subset induces a connected subgraph.

Results: The main result is an efficient O(IlogI)-time algorithm for the special case of the CFE problem. The algorithm can find a plane embedding that satisfies the given families, if one exists. The research also proves that the general problem is NP-complete.

Implications: The CFE problem has practical applications in various fields, such as topological information recovery, geographical data analysis, and VLSI design. The efficient algorithm presented in this research can help solve these problems more quickly and effectively.

Link to Article: https://arxiv.org/abs/0102007v1 Authors: arXiv ID: 0102007v1