Does anyone know any related topic about this problem?
Given a planar graph $G$. Let $C_f=\{C:\text{circuit } C \text{ is a face in some planar embedding}\}$. Find $C \in C_f$ with miximum(minimum) length. The length of a face is defined as the number of unique edges on its boundary.
I have done some research:
(1) 3-connected planars have a unique embedding. We only have to consider non-3-connected graphs.
(2) Face cycle test algorithm. Test if an arbitrary cycle is a face cycle. A related question is here, which I find a related paper: Simić, S. K. (1973). A NOTE ON FACES AND CYCLES. http://www.jstor.org/stable/43668032
Is there any solution other than enumerating all $C\in G$ and apply face cycle test?
I find a paper about finding max face length across all combinatorial embeddings:
Giordano Da Lozzo, Vít Jelínek, Jan Kratochvíl, and Ignaz Rutter. 2014. Planar Embeddings with Small and Uniform Faces. Algorithms and Computation: 25th International Symposium. https://doi.org/10.1007/978-3-319-13075-0_50
[Edited] I later found this is not what I thought it was. What I want to solve is the maximum max face across all embeddings, but this paper finds minimum max face across all embeddings.
mine: $\max\limits_{\mathcal{E}}\max\limits_{c \in C_f(\mathcal{E})}|c|=\max\limits_{c \text{ is a face in some } \mathcal{E}}|c|$
the paper: $\min\limits_{\mathcal{E}}\max\limits_{c \in C_f(\mathcal{E})}|c|$