“K-outerplanar graph”的意思、由来-开放百科全书

In graph theory, a k-outerplanar graph is a planar graph that has a planar embedding in which the vertices belong to at most

concentric layers. The outerplanarity index of a planar graph is the minimum value of

for which it is

-outerplanar.

Definition

An outerplanar graph (or 1-outerplanar graph) has all of its vertices on the unbounded (outside) face of the graph. A 2-outerplanar graph is a planar graph with the property that, when the vertices on the unbounded face are removed, the remaining vertices all lie on the newly formed unbounded face. And so on.

More formally, a graph is

-outerplanar if it has a planar embedding such that, for every vertex, there is an alternating sequence of at most

faces and

vertices of the embedding, starting with the unbounded face and ending with the vertex, in which each consecutive face and vertex are incident to each other.

Properties and applications

The

-outerplanar graphs have treewidth at most

.^[1] However, some bounded-treewidth planar graphs such as the nested triangles graph may be

-outerplanar only for very large

, linear in the number of vertices.

In connection with the GNRS conjecture on metric embedding of minor-closed graph families, the

-outerplanar graphs are one of the most general classes of graphs for which the conjecture has been proved.^[3]

A conjectured converse of Courcelle's theorem, according to which every graph property recognizable on graphs of bounded treewidth by finite state tree automata is definable in the monadic second-order logic of graphs, has been proven for the

-outerplanar graphs.^[4]

Recognition

The smallest value of

for which a given graph is

-outerplanar (its outerplanarity index) can be computed in quadratic time.^[5]

References

1. ^{{citation | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender | doi = 10.1016/S0304-3975(97)00228-4 | issue = 1-2 | journal = Theoretical Computer Science | mr = 1647486 | pages = 1–45 | title = A partial

-arboretum of graphs with bounded treewidth | volume = 209 | year = 1998}}
2. ^{{citation | last = Baker| first = B. | authorlink = Brenda Baker | journal = Journal of the ACM | title = Approximation algorithms for NP-complete problems on planar graphs | volume = 41 | issue = 1 | year = 1994 | pages = 153–180 | doi = 10.1145/174644.174650}}.
3. ^{{citation | last1 = Chekuri | first1 = Chandra | last2 = Gupta | first2 = Anupam | last3 = Newman | first3 = Ilan | last4 = Rabinovich | first4 = Yuri | last5 = Sinclair | first5 = Alistair | author5-link = Alistair Sinclair | doi = 10.1137/S0895480102417379 | issue = 1 | journal = SIAM Journal on Discrete Mathematics | mr = 2257250 | pages = 119–136 | title = Embedding

-outerplanar graphs into

| volume = 20 | year = 2006}}
4. ^{{citation | last1 = Jaffke | first1 = Lars | last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender | last3 = Heggernes | first3 = Pinar | author3-link = Pinar Heggernes | last4 = Telle | first4 = Jan Arne | doi = 10.1016/j.ejc.2017.06.025 | journal = European Journal of Combinatorics | mr = 3692146 | pages = 191–234 | title = Definability equals recognizability for

-outerplanar graphs and

-chordal partial

-trees | volume = 66 | year = 2017}}
5. ^{{citation | last = Kammer | first = Frank | editor1-last = Arge | editor1-first = Lars | editor2-last = Hoffmann | editor2-first = Michael | editor3-last = Welzl | editor3-first = Emo | contribution = Determining the smallest

such that

-outerplanar | doi = 10.1007/978-3-540-75520-3_33 | pages = 359–370 | publisher = Springer | series = Lecture Notes in Computer Science | title = Algorithms: ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings | volume = 4698 | year = 2007}}