Apex graph

Last updated June 05, 2024

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs $K 5$ or $K 3,3$ , every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

Characterization and recognition

Apex graphs are closed under the operation of taking minors: contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if $G$ is an apex graph with apex $v$ , then any contraction or removal that does not involve $v$ preserves the planarity of the remaining graph, as does any edge removal of an edge incident to $v$ . If an edge incident to $v$ is contracted, the effect on the remaining graph is equivalent to the removal of the other endpoint of the edge. And if $v$ itself is removed, any other vertex may be chosen as the apex.^[5]

By the Robertson–Seymour theorem, because they form a minor-closed family of graphs, the apex graphs have a forbidden graph characterization. There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor. These graphs are forbidden minors for the property of being an apex graph. Any other graph $G$ is an apex graph if and only if none of the forbidden minors is a minor of $G$ . These forbidden minors include the seven graphs of the Petersen family, three disconnected graphs formed from the disjoint unions of two of $K 5$ and $K 3,3$ , and many other graphs. However, a complete description of them remains unknown.^[5]^[6]

Despite the complete set of forbidden minors remaining unknown, it is possible to test whether a given graph is an apex graph, and if so, to find an apex for the graph, in linear time. More generally, for any fixed constant $k$ , it is possible to recognize in linear time the $k$ -apex graphs, the graphs in which the removal of some carefully chosen set of at most $k$ vertices leads to a planar graph.^[7] If $k$ is variable, however, the problem is NP-complete.^[8]

Chromatic number

Every apex graph has chromatic number at most five: the underlying planar graph requires at most four colors by the four color theorem, and the remaining vertex needs at most one additional color. Robertson, Seymour & Thomas (1993a) used this fact in their proof of the case $k = 6$ of the Hadwiger conjecture, the statement that every 6-chromatic graph has the complete graph $K 6$ as a minor: they showed that any minimal counterexample to the conjecture would have to be an apex graph, but since there are no 6-chromatic apex graphs such a counterexample cannot exist.

Unsolved problem in mathematics:

Is every 6-vertex-connected $K 6$ -minor-free graph an apex graph?

(more unsolved problems in mathematics)

Jørgensen (1994) conjectured that every 6-vertex-connected graph that does not have $K 6$ as a minor must be an apex graph. If this were proved, the Robertson–Seymour–Thomas result on the Hadwiger conjecture would be an immediate consequence.^[2] Jørgensen's conjecture remains unproven.^[9] However, if false, it has only finitely many counterexamples.^[10]

Local treewidth

A graph family $F$ has bounded local treewidth if the graphs in $F$ obey a functional relationship between diameter and treewidth: there exists a function $f$ such that the treewidth of a diameter- $d$ graph in $F$ is at most $f (d)$ . The apex graphs do not have bounded local treewidth: the apex graphs formed by connecting an apex vertex to every vertex of an $n \times n$ grid graph have treewidth $n$ and diameter 2, so the treewidth is not bounded by a function of diameter for these graphs. However, apex graphs are intimately connected to bounded local treewidth: the minor-closed graph families $F$ that have bounded local treewidth are exactly the families that have an apex graph as one of their forbidden minors.^[4] A minor-closed family of graphs that has an apex graph as one of its forbidden minors is known as apex-minor-free. With this terminology, the connection between apex graphs and local treewidth can be restated as the fact that apex-minor-free graph families are the same as minor-closed graph families with bounded local treewidth.

The concept of bounded local treewidth forms the basis of the theory of bidimensionality, and allows for many algorithmic problems on apex-minor-free graphs to be solved exactly by a polynomial-time algorithm or a fixed-parameter tractable algorithm, or approximated using a polynomial-time approximation scheme.^[11] Apex-minor-free graph families obey a strengthened version of the graph structure theorem, leading to additional approximation algorithms for graph coloring and the travelling salesman problem.^[12] However, some of these results can also be extended to arbitrary minor-closed graph families via structure theorems relating them to apex-minor-free graphs.^[13]

Embeddings

If $G$ is an apex graph with apex $v$ , and $τ$ is the minimum number of faces needed to cover all the neighbors of $v$ in a planar embedding of $G \ {v},$ then $G$ may be embedded onto a two-dimensional surface of genus $τ - 1$ : simply add that number of bridges to the planar embedding, connecting together all the faces into which $v$ must be connected. For instance, adding a single vertex to an outerplanar graph (a graph with $τ = 1$ ) produces a planar graph. When $G \ {v}$ is 3-connected, his bound is within a constant factor of optimal: every surface embedding of $G$ requires genus at least $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}τ/160$ . However, it is NP-hard to determine the optimal genus of a surface embedding of an apex graph.^[14]

By using SPQR trees to encode the possible embeddings of the planar part of an apex graph, it is possible to compute a drawing of the graph in the plane in which the only crossings involve the apex vertex, minimizing the total number of crossings, in polynomial time.^[15] However, if arbitrary crossings are allowed, it becomes NP-hard to minimize the number of crossings, even in the special case of apex graphs formed by adding a single edge to a planar graph.^[16]

Apex graphs are also linklessly embeddable in three-dimensional space: they can be embedded in such a way that each cycle in the graph is the boundary of a disk that is not crossed by any other feature of the graph.^[17] A drawing of this type may be obtained by drawing the planar part of the graph in a plane, placing the apex above the plane, and connecting the apex by straight-line edges to each of its neighbors. Linklessly embeddable graphs form a minor-closed family with the seven graphs in the Petersen family as their minimal forbidden minors;^[1] therefore, these graphs are also forbidden as minors for the apex graphs. However, there exist linklessly embeddable graphs that are not apex graphs.

YΔY-reducibility

A connected graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of steps, each of which is a Δ-Y or Y-Δ transform, the removal of a self-loop or multiple adjacency, the removal of a vertex with one neighbor, and the replacement of a vertex of degree two and its two neighboring edges by a single edge.^[3]

Like the apex graphs and the linkless embeddable graphs, the YΔY-reducible graphs are closed under graph minors. And, like the linkless embeddable graphs, the YΔY-reducible graphs have the seven graphs in the Petersen family as forbidden minors, prompting the question of whether these are the only forbidden minors and whether the YΔY-reducible graphs are the same as the linkless embeddable graphs. However, Neil Robertson provided an example of an apex graph that is not YΔY-reducible. Since every apex graph is linkless embeddable, this shows that there are graphs that are linkless embeddable but not YΔY-reducible and therefore that there are additional forbidden minors for the YΔY-reducible graphs.^[3]

Robertson's apex graph is shown in the figure. It can be obtained by connecting an apex vertex to each of the degree-three vertices of a rhombic dodecahedron, or by merging two diametrally opposed vertices of a four-dimensional hypercube graph. Because the rhombic dodecahedron's graph is planar, Robertson's graph is an apex graph. It is a triangle-free graph with minimum degree four, so it cannot be changed by any YΔY-reduction.^[3]

Nearly planar graphs

The 16-vertex Mobius ladder, an example of a nearly planar graph. Moebius-ladder-16.svg — The 16-vertex Möbius ladder, an example of a nearly planar graph.

If a graph is an apex graph, it is not necessarily the case that it has a unique apex. For instance, in the minor-minimal nonplanar graphs K₅ and K_3,3, any of the vertices can be chosen as the apex. Wagner ( 1967 , 1970 ) defined a nearly planar graph to be a nonplanar apex graph with the property that all vertices can be the apex of the graph; thus, K₅ and K_3,3 are nearly planar. He provided a classification of these graphs into four subsets, one of which consists of the graphs that (like the Möbius ladders) can be embedded onto the Möbius strip in such a way that the single edge of the strip coincides with a Hamiltonian cycle of the graph. Prior to the proof of the four color theorem, he proved that every nearly planar graph can be colored with at most four colors, except for the graphs formed from a wheel graph with an odd outer cycle by replacing the hub vertex with two adjacent vertices, which require five colors. Additionally, he proved that, with a single exception (the eight-vertex complement graph of the cube) every nearly planar graph has an embedding onto the projective plane.

However, the phrase "nearly planar graph" is highly ambiguous: it has also been used to refer to apex graphs,^[18] graphs formed by adding one edge to a planar graph,^[19] and graphs formed from a planar embedded graph by replacing a bounded number of faces by "vortexes" of bounded pathwidth,^[20] as well as for other less precisely-defined sets of graphs.

Related graph classes

An abstract graph is said to be n-apex if it can be made planar by deleting n or fewer vertices. A 1-apex graph is also said to be apex.

According to Lipton et al. (2018), a graph is edge-apex if there is some edge in the graph that can be deleted to make the graph planar. A graph is contraction-apex if there is some edge in the graph that can be contracted to make the graph planar.

In general, if X is a class of graphs, an "apex-X" graph is a graph that can be brought into the class X by deleting some one vertex. For example, an apex-cograph is a graph G that has a vertex v such that G―v is a cograph.

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, the Robertson–Seymour theorem states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is closed under minors can be defined by a finite set of forbidden minors, in the same way that Wagner's theorem characterizes the planar graphs as being the graphs that do not have the complete graph K₅ or the complete bipartite graph K_3,3 as minors.

In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges, vertices and by contracting edges.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

<span class="mw-page-title-main">Paul Seymour (mathematician)</span> British mathematician

Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, the Hadwiger number of an undirected graph $G$ is the size of the largest complete graph that can be obtained by contracting edges of $G$ . Equivalently, the Hadwiger number $h (G)$ is the largest number $n$ for which the complete graph $K n$ is a minor of $G$ , a smaller graph obtained from $G$ by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of $G$ or the homomorphism degree of $G$ . It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of $G$ .

Colin de Verdière's invariant is a graph parameter $for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.$

<span class="mw-page-title-main">Wagner's theorem</span> On forbidden minors in planar graphs

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K₅ nor K_3,3. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly $k$ are called $k$ -trees, and the graphs with treewidth at most $k$ are called partial $k$ -trees. Many other well-studied graph families also have bounded treewidth.

In graph theory, a path decomposition of a graph $G$ is, informally, a representation of $G$ as a "thickened" path graph, and the pathwidth of $G$ is a number that measures how much the path was thickened to form $G$ . More formally, a path-decomposition is a sequence of subsets of vertices of $G$ such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

<span class="mw-page-title-main">Branch-decomposition</span> Hierarchical clustering of graph edges

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

<span class="mw-page-title-main">Clique-sum</span> Gluing graphs at complete subgraphs

In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.

In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph $K 6$ . The Petersen family is named after Danish mathematician Julius Petersen, the namesake of the Petersen graph.

In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994.

In graph theory, a branch of mathematics, Halin's grid theorem states that the infinite graphs with thick ends are exactly the graphs containing subdivisions of the hexagonal tiling of the plane. It was published by Rudolf Halin, and is a precursor to the work of Robertson and Seymour linking treewidth to large grid minors, which became an important component of the algorithmic theory of bidimensionality.

<span class="mw-page-title-main">Planar cover</span> Graph theory concept

In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.

References

Abraham, Ittai; Gavoille, Cyril (2006), "Object location using path separators", Proc. 25th ACM Symposium on Principles of Distributed Computing (PODC '06), pp. 188–197, doi:10.1145/1146381.1146411, S2CID 8844836 .
Archdeacon, Dan; Bonnington, C.P.C. Paul (2004), "Obstructions for embedding cubic graphs on the spindle surface", Journal of Combinatorial Theory, Series B , 91 (2): 229–252, doi: 10.1016/j.jctb.2004.02.001 , hdl: 2292/5158 .
Cabello, Sergio; Mohar, Bojan (2010), "Adding one edge to planar graphs makes crossing number hard", Proc. 26th ACM Symposium on Computational Geometry (SoCG '10) (PDF), pp. 68–76, doi:10.1145/1810959.1810972, S2CID 17271180, archived from the original (PDF) on 2012-03-14, retrieved 2010-08-02.
Chimani, Markus; Gutwenger, Carsten; Mutzel, Petra; Wolf, Christian (2009), "Inserting a vertex into a planar graph", Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 375–383.
Demaine, Erik D.; Hajiaghayi, Mohammad Taghi (2004), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica , 40 (3): 211–215, doi:10.1007/s00453-004-1106-1, S2CID 390856 .
Demaine, Erik D.; Hajiaghayi, Mohammad Taghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA '05), pp. 590–601, archived from the original on 2018-12-11, retrieved 2010-08-02.
Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2009), "Approximation algorithms via structural results for apex-minor-free graphs" (PDF), Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09), Lecture Notes in Computer Science, vol. 5555, Springer-Verlag, pp. 316–327, doi:10.1007/978-3-642-02927-1_27 .
Eppstein, David (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica , 27 (3): 275–291, arXiv: math.CO/9907126 , doi:10.1007/s004530010020, S2CID 3172160 .
Frick, Markus; Grohe, Martin (2001), "Deciding first-order properties of locally tree-decomposable structures", Journal of the ACM , 48 (6): 1184–1206, arXiv: cs/0004007 , doi:10.1145/504794.504798, S2CID 999472 .
Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica , 23 (4): 613–632, arXiv: math.CO/0001128 , doi:10.1007/s00493-003-0037-9, S2CID 11751235 .
Gupta, A.; Impagliazzo, R. (1991), "Computing planar intertwines", Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91), IEEE Computer Society, pp. 802–811, doi:10.1109/SFCS.1991.185452, S2CID 209133 .
Jørgensen, Leif K. (1994), "Contractions to K₈", Journal of Graph Theory, 18 (5): 431–448, doi:10.1002/jgt.3190180502 . As cited by Robertson,Seymour,andThomas (1993a, 1993c).
Kawarabayashi, Ken-ichi (2009), "Planarity allowing few error vertices in linear time" (PDF), Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09), IEEE Computer Society, pp. 639–648, doi:10.1109/FOCS.2009.45, S2CID 11647021 .
Kawarabayashi, Ken-ichi; Norine, Serguei; Thomas, Robin; Wollan, Paul (2012), $K_{6}$ minors in large 6-connected graphs, arXiv: 1203.2192 , Bibcode:2012arXiv1203.2192K .
Lewis, John M.; Yannakakis, Mihalis (1980), "The node-deletion problem for hereditary properties is NP-complete", Journal of Computer and System Sciences , 20 (2): 219–230, doi: 10.1016/0022-0000(80)90060-4 .
Lipton, Max; Mackall, Eoin; Mattman, Thomas W.; Pierce, Mike; Robinson, Samantha; Thomas, Jeremy; Weinschelbaum, Ilan (2018), "Six variations on a theme: Almost planar graphs", Involve: A Journal of Mathematics, 11 (3): 413–448, arXiv: 1608.01973 , doi:10.2140/involve.2018.11.413, S2CID 119740613 .
Mohar, Bojan (2001), "Face covers and the genus problem for apex graphs" (PDF), Journal of Combinatorial Theory, Series B , 82 (1): 102–117, doi:10.1006/jctb.2000.2026, archived from the original (PDF) on 2017-09-22, retrieved 2010-08-02.
Pierce, Mike (2014), Searching for and classifying the finite set of minor-minimal non-apex graphs (PDF), Honours thesis, California State University, Chico.
Robertson, Neil; Seymour, Paul; Thomas, Robin (1993a), "Hadwiger's conjecture for K₆-free graphs" (PDF), Combinatorica , 13 (3): 279–361, doi:10.1007/BF01202354, S2CID 9608738 .
Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993b), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society , 28 (1): 84–89, arXiv: math/9301216 , doi:10.1090/S0273-0979-1993-00335-5, MR 1164063, S2CID 1110662 .
Robertson, Neil; Seymour, Paul; Thomas, Robin (1993c), "A survey of linkless embeddings", in Robertson, Neil; Seymour, Paul (eds.), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors (PDF), Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 125–136.
Truemper, Klaus (1992), Matroid Decomposition (PDF), Academic Press, pp. 100–101, archived from the original (PDF) on 2017-08-29, retrieved 2010-08-02.
Wagner, Klaus (1967), "Fastplättbare Graphen", Journal of Combinatorial Theory (in German), 3 (4): 326–365, doi: 10.1016/S0021-9800(67)80103-0 .
Wagner, Klaus (1970), "Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I", Journal of Combinatorial Theory (in German), 9 (1): 27–43, doi: 10.1016/S0021-9800(70)80052-7 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[linkless-1] 1 2 Robertson, Seymour & Thomas (1993b).

[rst93-2] 1 2 Robertson, Seymour & Thomas (1993a).

[t92-3] 1 2 3 4 Truemper (1992).

[local-4] 1 2 Eppstein (2000); Demaine & Hajiaghayi (2004).

[gi91-5] 1 2 Gupta & Impagliazzo (1991).

[FOOTNOTEPierce2014-6] Pierce (2014).

[7] Kawarabayashi (2009).

[8] Lewis & Yannakakis (1980).

[9] "Jorgensen's Conjecture", Open Problem Garden, retrieved 2016-11-13.

[FOOTNOTEKawarabayashiNorineThomasWollan2012-10] Kawarabayashi et al. (2012).

[11] Eppstein (2000); Frick & Grohe (2001); Demaine & Hajiaghayi (2005).

[12] Demaine, Hajiaghayi & Kawarabayashi (2009).

[13] Grohe (2003).

[14] Mohar (2001).

[15] Chimani et al. (2009).

[16] Cabello & Mohar (2010).

[17] Robertson, Seymour & Thomas (1993c).

[18] Robertson, Seymour & Thomas (1993c); Eppstein (2000).

[19] Archdeacon & Bonnington (2004).

[20] Abraham & Gavoille (2006).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]