Given a spanning tree of a planar graph , the co-tree of is the spanning tree of the dual graph * with edge set (() − ( ))* . Grünbaum conjectured in 1970 that every planar 3-connected graph contains a spanning tree such that both and its co-tree have maximum degree at most 3. While Grünbaum's conjecture remains open, Schmidt and the author recently improved the upper bound on the maximum degree from 5 (Biedl 2014) to 4. In this paper, we modify this approach taking a further step towards Grünbaum's conjecture. We again obtain a spanning tree such that both and its co-tree have maximum degree at most 4 and, additionally, an upper bound on the number of vertices of degree 4 of and its co-tree.
of a 4-tree whose co-tree is a 4-tree. In this paper, we additionally give upper bounds on the number of vertices of degree 4 in both the tree and the co-tree. The approach is similar to the one in [11]. We use a diferent candidate graph, show that it meets all necessary conditions and then apply a method similar to the one in [11]. We observe that only under specific local conditions vertices of degree 4 might arise. Thus, we are able to count them.
We fix a minimal Schnyder wood of . gives rise to a Schnyder wood of the suspended dual (a graph that difers form the dual graph only on the outer face). Also, every Schnyder wood has three compatible ordered path partitions, denoted by ,+1, ∈ {1, 2, 3}. We define and explain those concepts in Section 2.
The upper bound on the number of degree-4-vertices in and ¬ * is then given by min{2′,3, ′ + 2 − ′3,1, ′ + 2 − ′1,2} − 1 and min{2,3, − 3,1, − 1,2} − 1, respectively. Here (′) is the order of the primal (dual) graph, ,+1 (′,+1) is the number of singletons in ,+1 of the primal (dual) graph and ,+1 (′,+1) is the number of paths in ,+1 of the primal (dual) graph.
Our arguments work symmetrically for any choice of two colors. Thus, we obtain for example that if one of the compatible ordered path partitions of the minimal Schnyder wood of the dual graph has only one singleton (which is the minimum number of singletons), then there exists a spanning tree of maximum degree at most 3 such that its co-tree has maximum degree at most 4.
We discuss Schnyder woods, their lattice structure and ordered path partitions in Section 2 and our main result in Section 3. Due to space limitations some proofs are omitted or only sketched.
We only consider simple undirected graphs. A graph is plane if it is planar and embedded into the Euclidean plane without intersecting edges. The neighborhood of a vertex set is the union of the neighborhoods of vertices in . Although parts of this paper use orientation on edges, we will always let denote the undirected edge {, }.
Let := {1, 2, 3} be a set of three vertices of the outer face boundary of a plane graph in clockwise order (but not necessarily consecutive). We call 1, 2 and 3 roots. The suspension of is the graph obtained from by adding at each root of a half-edge pointing into the outer face. With a little abuse of notation, we define a half-edge as an arc starting at a vertex but with no defined end vertex. A plane graph is -internally 3-connected if the graph obtained from the suspension of by making the three half-edges incident to a common new vertex inside the outer face is 3-connected. The class of -internally 3-connected plane graphs properly contains all 3-connected plane graphs.
Definition 1 (Felsner [12]). Let = {1, 2, 3} and be the suspension of a -internally 3-connected plane graph . A Schnyder wood of is an orientation and coloring of the edges of (including the half-edges) with the colors 1,2,3 (red, green, blue) such that 1. Every edge is oriented in one direction (we say is unidirected) or in two opposite directions (we say is bidirected). Every direction of an edge is colored with one of the three colors 1,2,3 (we say an edge is -colored if one of its directions has color ) such that the two colors and of every bidirected edge are distinct (we call such an edge --colored). Throughout the paper, we assume modular arithmetic on the colors 1,2,3. 2. For every color , the half-edge at is unidirected, outgoing and -colored. 3. Every vertex has exactly one outgoing edge of every color. The outgoing 1-, 2-, 3-colored edges 1, 2, 3 of occur in clockwise order around . For every color , every incoming -colored edge of is contained in the clockwise sector around from +1 to − 1 (Figure 1i). 4. No inner face boundary contains a directed cycle in one color.
3
For a Schnyder wood and color , let be the directed graph that is induced by the directed edges of color . The following result justifies the name of Schnyder woods.
Lemma 1 ([13, 14]). For every color of a Schnyder wood of , is a directed spanning tree of in which all edges are oriented towards the root .
Lemma 2 (Felsner [15]). Let − 1 be obtained from by reversing the orientation of all its edges. For every ∈ {1, . . . , 3}, − 1 ∪ −+11 ∪ +2 is acyclic.
Let be a -internally 3-connected plane graph. Any Schnyder wood of induces a Schnyder wood of a slightly modified planar dual of in the following way [16, 17] (see [18, p. 30] for an earlier variant of this result given without proof). As common for plane duality, we will use the plane dual operator * to switch between primal and dual objects (also on sets of objects). − 1+1).
Extend the three half-edges of to non-crossing infinite rays and consider the planar dual of this plane graph. Since the infinite rays partition the outer face of into three parts, this dual contains a triangle with vertices 1, 2 and 3 instead of the outer face vertex * such that * is not incident to for every (Figure 1ii). Let the suspended dual * of be the graph obtained from this dual by adding at each vertex of {1, 2, 3} a half-edge pointing into the outer face.
Consider the superposition of and its suspended dual * such that exactly the primal dual pairs of edges cross (here, for every 1 ≤ ≤ 3, the half-edge at crosses the dual edge Definition 2. For any Schnyder wood of , define the orientation and coloring * of the suspended dual * as follows (Figure 1ii): 1. For every unidirected ( − 1)-colored edge or half-edge of , color * with the two colors and + 1 such that points to the right of the -colored direction. 2. Vice versa, for every -( + 1)-colored edge of , ( − 1)-color * unidirected such that * points to the right of the -colored direction. 3. For every color , make the half-edge at unidirected, outgoing and -colored.
The following lemma states that * is indeed a Schnyder wood of the suspended dual. The vertices 1, 2 and 3 are called the roots of * .
Lemma 3 ([19][17, Prop. 3]). For every Schnyder wood of , * is a Schnyder wood of * .
Since * * = , Lemma 3 gives a bijection between the Schnyder woods of and the ones of * . Let the completion ̃︀ of be the plane graph obtained from the superposition of and * by subdividing each pair of crossing (half-)edges with a new vertex, which we call a crossing vertex (Figure 1ii).
Any Schnyder wood of implies the following natural orientation and coloring ̃︀ of its completion ̃︀: For any edge ∈ ( ) ∪ ( * ), let be the crossing vertex of that subdivides and consider the coloring of in either or * . If is outgoing of and -colored, we direct ∈ (̃︀) toward and -color it; analogously, if is outgoing of and -colored, we direct ∈ (̃︀) toward and -color it. In the case that is unidirected, say w.l.o.g. incoming at and -colored, we direct ∈ (̃︀) toward and -color it. The three half-edges of * inherit the orientation and coloring of * for ̃︀ . By Definition 2, the construction of ̃︀ implies immediately the following corollary.
Corollary 1. Every crossing vertex of ̃︀ has one outgoing edge and three incoming edges and the latter are colored 1, 2 and 3 in counterclockwise direction.
Using results on orientations with prescribed outdegrees on the respective completions, Felsner and Mendez [20, 14] showed that the set of Schnyder woods of a planar suspension forms a distributive lattice. The order relation of this lattice relates a Schnyder wood of to a second Schnyder wood if the former can be obtained from the latter by reversing the orientation of a directed clockwise cycle in the completion. This gives the following lemma. Lemma 4 ([20, 14]). For the minimal element of the lattice of all Schnyder woods of , ̃︀ contains no clockwise directed cycle.
We call the minimal element of the lattice of all Schnyder woods of the minimal Schnyder wood of .
We denote paths as tuples of vertices such that consecutive vertices in the tuple are adjacent in the path. If a path consists of only one vertex , we might also write = . The concatenation of two paths 1 and 2 we denote by 12.
Definition 3. For any ∈ {1, 2, 3} and any {1, 2, 3}-internally 3-connected plane graph , an ordered path partition = (0, . . . , ) of with base-pair ( , +1) is a tuple of induced paths such that their vertex sets partition () and the following holds for every ∈ {0, . . . , − 1}, where := ⋃︀
=0 () and the contour is the clockwise walk from +1 to on the outer face of [].
1. 0 is the clockwise path from to +1 on the outer face boundary of , and = +2. 2. Every vertex in has a neighbor in () ∖ . 3. is a path.
4. Every vertex in has at most one neighbor in +1.
Remark 1. Our definition of an ordered path partition = (0, . . . , ) is essentially the definition of Badent et al. [ 21], in which the paths need to be induced (this is not explicitly stated in [21], but used in the proof of their Theorem 5).
By Definition 31 and 32, contains for every and every vertex ∈ a path from to +2 that intersects only in . Since is plane, we conclude the following.
Lemma 5. Every path of an ordered path partition is embedded into the outer face of [− 1] for every 1 ≤ ≤ . 2.3.1. Compatible Ordered Path Partitions We describe a connection between Schnyder woods and ordered path partitions that was first given by Badent et al. [21, Theorem 5] and then revisited by Alam et al. [22, Lemma 1]. Definition 4. Let ∈ {1, 2, 3} and be any Schnyder wood of the suspension of . As proven in [22, arXiv version, Section 2.2], the inclusion-wise maximal -( + 1)-colored paths of then form an ordered path partition of with base pair ( , +1), whose order is a linear extension of the partial order given by reachability in the acyclic graph − 1 ∪ −+11 ∪ +2; we call this special ordered path partition compatible with and denote it by ,+1.
For example, for the Schnyder wood given in Figure 1ii, 2,3 consists of the six maximal 2-3-colored paths, of which four are single vertices. We denote each path ∈ ,+1 by := (1 , . . . , ) such that 2 is outgoing -colored at .
1 1
Let be as in Definition 3. By Definition 33 and Lemma 5, every path = (1 , . . . , ) of an ordered path partition satisfying ∈ {1, . . . , } has a neighbor 0 ∈ − 1 that is closest to +1 and a diferent neighbor +1 ∈ − 1 that is closest to . We call 0 the left neighbor of , +1 the right neighbor of and := 0 +1 the extension of ; we omit superscripts if these are clear from the context. For 0 < ≤ , let the path cover an edge or a vertex if or is contained in − 1, but not in , respectively.
For the remainder of this section let be a {1, 2, 3}-internally 3-connected plane graph of order with a dual graph of order ′ and a minimal Schnyder wood . Define ,+1 (′,+1) to be the number of singletons in ,+1 of the primal (dual) graph and ,+1 (′,+1) to be the number of paths in ,+1 of the primal (dual) graph. We show that we can find a tree and co-tree with maximum degree at most four such that the number of vertices with degree four in the tree is at most min{2′,3, ′ + 2 − ′3,1, ′ + 2 − ′1,2} − 1 and the number of vertices with degree four in the co-tree is at most min{2,3, − 3,1, − 1,2} − 1.
We start with two lemmas on the structure of Schnyder woods. Then, we define our candidate graphs and ′ that have the same structural properties. We show that they both have maximum degree at most 3 and that for every edge of either the edge itself is in or its dual is in ′. We observe that for a cycle in the path with the highest index in 2,3 that contains a vertex of needs to be a singleton. This is the key observation that leads to the upper bound on the number of degree-4-vertices. Then, we eventually prove the main theorem. The proof of the main theorem uses similar tools as presented in [11]. However, our candidate graph which is diferent from the one used in [ 11] and the aforementioned observation additionally yield the upper bound on the number of vertices of degree 4.
Lemma 6 ([11]). Let 2,3 = (0, . . . , ) be the ordered path partition that is compatible with . Let := (1, . . . , ) ̸= 0 be a path of 2,3 and 0 and +1 be its left and right neighbor. Then, 01, +1 ∈ (), every edge ∈/ {01, +1} with ∈ and ∈ − 1 is unidirected, 1-colored and incoming at and is contained in the path of − 1 between 0 and +1 excluding both.
Lemma 7 (Di Battista et al. [16]). The boundary of every internal face of can be partitioned into six paths 1,3, 2,3, 2,1, 3,1, 3,2 and 1,2 which appear in that clockwise order. For those paths the following holds (Figure 2).
1. , consists of one edge which is either unidirected -colored, unidirected -colored or -colored. Color is directed in clockwise direction and color in counterclockwise direction around . 2. , consists of a possibly empty sequence of --colored edges such that color is directed clockwise around .
Definition 5. Let be an internal face. Define = (1, . . . , ) to be the path consisting of the edges on the boundary of that are 2-3-colored or unidirected 3-colored such that color 3 is directed counterclockwise around . By Lemma 7, is indeed a path. It consists of 2,3 and possibly 1,3 (Figure 2). Let be such that color 3 is directed from 1 to . For a vertex let () be the neighbor such that () is the clockwise first incoming 1-colored edge at . Define to be the subgraph of with vertex set () and the edge set given by 1,3 1,2
2,3 * 3,2 2,1 3,1
Observe that the edges added by Condition 3 are 2-3-colored. Define ′ the same way for * . See Figure 3 for illustration.
Observe that for = (1, . . . , ) we have ( * ) * = (− 1)* (Figure 2). By Condition 3, − 1 ∈/ ( ) and, by Condition 2, (− 1)* ∈ ( ′). Similar observations and a complete case distinction that covers all possible orientations and colorings of an edge of then yield the following lemma.
Lemma 8. For an edge ∈ () we have that ∈ ( ) if and only if * ∈/ ( ′). And thus, ′ = ¬ * ∪ {12, 23, 31}.
Lemma 9. and ′ both have maximum degree at most 3.
Proof. We show that has maximum degree at most 3. The arguments work similarly for ′. Consider a vertex ∈ ().
Assume that is incident to a 2-3-colored edge ∈ () that is incoming 3-colored at . Then, either Definition 53 or 4 applies to . We give a short argument that in both cases there is no edge in the clockwise sector around between and the outgoing 3-colored edge. If Definition 54 applies to , then is on the clockwise path from 2 to 3 on the boundary of the outer face, and the claim obviously holds.
Otherwise, Definition 53 applies to . Assume, for the sake of contradiction, that there is an edge in the clockwise interval around between and the outgoing 3-colored edge. Let ′ be the clockwise first such edge. By Definition 13, ′ is unidirected 1-colored and incoming at . and ′ are on a common face . The path = (1, . . . , ) contains . Since ′ is not outgoing 3-colored at , we obtain that − 1 = and thus, ∈/ (), a contradiction.
By Definition 13, the unidirected incoming 1-colored edges occur in the clockwise sector around between and the outgoing 3-colored edge. Thus, there is no unidirected incoming 1-colored edge at . Hence, by Definition 5, the outgoing 1-colored edge and the outgoing 3-colored edge at are the only additional edges incident to that might be in (). This yields that deg () ≤ 3.
So assume that is not incident to a 2-3-colored edge ∈ () that is incoming 3-colored at . Then, by Definition 5, there are at most three edges incident to that might be in (), namely (), the outgoing 3-colored and the outgoing 1-colored edge. Thus, we have deg () ≤ 3.
Definition 6. Let be a cycle in . Let 2,3 = (0, . . . , ) be the compatible ordered path partition of . Let be the path of maximal length in such that ⊆ with := max{ | ∩ () ̸= ∅}. We call the index maximal subpath of . Denote by the set of all index maximal subpaths.
By Lemma 6, every path = (1, . . . , ) ∈ 2,3 is connected to − 1 only by 01 and edges incident to . Also, Definition 53 yields that if ≥ 2, then either 01 or 12 is not in . Hence, we obtain the following lemma.
Lemma 10. Let = (1, . . . , ) ∈ 2,3 be a path containing an index maximal subpath of a cycle in . Then, is a singleton, the edge from to its left neighbor 0 is 3-1-colored and in and the other edge in incident to 1 is (1)1. The same holds for ′. Definition 7. A singleton in 2,3 is a 1-2-singleton ( 2-singleton) if its outgoing 2-colored edge is 1-2-colored (unidirected) and its outgoing 3-colored edge is 3-1-colored.
Observe that, by Lemma 10, index maximal subpaths are either 1-2-singletons or 2-singletons. And, for a 1-2-singleton, the outgoing 2-colored edge and () coincide. Theorem 1. Let be a {1, 2, 3}-internally 3-connected plane graph of order with a dual graph of order ′ and a minimal Schnyder wood of . There is a 4-tree in such that ¬ * is a 4-tree. Also, the number of degree-4-vertices in is at most min{2′,3, ′ + 2 − ′3,1, ′ + 2 − ′1,2} − 1 and the number of degree-4-vertices in ¬ * is at most min{2,3, − 3,1, − 1,2} − 1. Sketch of proof. Let and ′ be as defined in Definition 5. Recall that, by Lemma 8, ∈ () if and only if * ∈/ (′), and thus ′ = ¬* ∪ {12, 23, 31}. As 12, 23 and 31 are not in * , they do not afect our desired trees. By Lemma 9, and ′ both have maximum degree at most 3. Observe that and ′ might both have cycles and are not necessarily connected (Figure 3).
We will therefore iteratively identify edges of cycles of such that ¬* ∪ {12, 23, 31} still has maximum degree at most four when those edges are deleted in . In order to do this, we iteratively define the set of edges ⊆ () that is deleted from . Then, we use the exact same arguments in order to define the set of edges ′ that is deleted from ′. We start with = ′ = ∅.
Let 2,3 = (0, . . . , ) be the compatible ordered path partition formed by the maximal 2-3-colored paths. We will consider paths that are the first (i.e. index minimal) path covering an index maximal subpath. For a path ∈ ∖ {} refer to with = min{ | covers an edge of the extension of } as the minimal-covering path of . Denote by the set of the minimal-covering paths of the paths of ∖ {}.
Observe that = 1 is the index maximal subpath of the outer face boundary and a 1-2singleton. There is no path in 2,3 that covers an edge of . Hence, in order to destroy the outer face cycle, we add the outgoing 3-colored edge of 1 to .
Next, we process the paths of in reverse order of 2,3, i.e., from highest to lowest index. Let = (1, . . . , ) ∈ , ∈ {1, . . . , } be the path under consideration. Let 1, . . . , be the index maximal paths for which is the minimal-covering path, ordered clockwise around the outer face of [− 1] (Figure 4). Let 1, . . . , be the faces incident to in counterclockwise order from the outgoing 3-colored edge to the outgoing 2-colored edge. We say that 1, . . . , are below and above 1, . . . , . Observe that since is minimal, if +1 = , then +1 is 1-2-colored [11, proof of Theorem 14].
0 1 1 1
2
3 2 4 3 5 4
+1 (2)
Remember that, by Lemma 10, () and the outgoing 3-colored edge are the only edges in that join with vertices of − 1.
Now, we select for each of the singletons ∈ {1, . . . , } either the outgoing 3-colored edge or () and add it to . Thus, after having processed every path in , a cycle in does not exist in − anymore. We aim for selecting those edges that have the smallest possible impact on the maximum degree of the dual graph. Hence, for a 2-singleton we always choose the edge (). Deleting this specific edge does not increase the degree of any face below (Figure 4). In detail we distinguish the following three cases.
Case 1: = (1, . . . , ) is not in . For every singleton ∈ {1, . . . , } ∖ {+1}, we add () to . If +1 = is a 2-singleton, we add () to . Otherwise, we add its outgoing 3-colored edge to (Figure 4).
Case 2: = 1 is an index maximal subpath and a 1-2-singleton. Then, we already have either 01 ∈ or 12 ∈ .
Case 2.1: 01 ∈ . We proceed as in Case 1.
Case 2.2: 12 ∈ . For every singleton ∈ {1, . . . , } that is a 2-singleton, we add () to . For every singleton ∈ {1, . . . , } ∖ {0} that is a 1-2-singleton, we add the outgoing 3-colored edge to . If 0 = 1 is a 1-2-singleton, then add its outgoing 2-colored edge to (Figure 5i).
Case 3: = 1 is an index maximal subpath and a 2-singleton. Then, we already added (1)1 to . For every singleton ∈ {1, . . . , }, we add () to . Observe that 12 is unidirected 2-colored and hence 2 ̸= (Figure 5ii).
1 1 0 2 0 2 (i) The situation in Case 2.2. (ii) The situation in Case 3.
As in [11, proof of Theorem 14] we observe that after having processed no more edges incident to 1, . . . , are added to . By Definition 32, the boundary of every with ∈ {1, . . . , } contains at most two edges that are in the union of the extensions of singletons in {1, . . . , }. In Case 1 and 2, for every ∈ {2, . . . , − 1}, we add at most one edge of the boundary of to . This implies that deg¬* +* (* ) ≤ 4 for every ∈ {2, . . . , − 1} (Figure 4 and 5i). The same holds for every ∈ {1, . . . , − 2} in Case 3 (Figure 5ii). Similar arguments as in [11, proof of Theorem 14] show that the degree of the remaining vertices of 1* , . . . , * does not exceed 4 in ¬* + * .
Also, those arguments yield that every degree-4-vertex * of ¬* + * such that is below a path of has at least one 1-2-singleton on its boundary such that * is above and either the outgoing 2-colored edge at or the outgoing 3-colored edge at is on the boundary of and in (Figure 4 and 5). In the following, we show that the vertices of ¬* + * that are not below a path of have maximum degree at most 3. Hence, the assignment of degree-4-vertices of ¬* + * to 1-2-singletons implied by the above relation is injective.
Now, we show that a vertex ′* of ¬* + * such that ′ is not below a path of has degree at most 3 in ¬* + * . If ′* is not incident to an edge of * , then we have that deg¬* +* ( ′* ) = deg¬* ( ′* ) ≤ 3. If ′* is incident to an edge of * , then ′* is below a path of . Such a path is either a 1-2-singleton or a 2-singleton. Hence, ′* does not have unidirected incoming 1-colored edges. We have that = 1 for a vertex 1 ∈ (). Assume that is a 1-2-singleton. Then, either 01 ∈ or 12 ∈ . And thus, ′* is either incident to (01)* or (12)* . If ′* is incident to (01)* ((12)* ), then the only edges incident to ′* that might be in ¬* are its outgoing 2-colored (3-colored) edge and its outgoing 1-colored edge, i.e., deg¬* ( ′* ) ≤ 2 and thus deg¬* +* ( ′* ) ≤ 3. So assume that is a 2-singleton. Then, ′* is incident to ( (1)1)* . This dual edge is 2-3-colored. As ′* does not have unidirected incoming 1-colored edges, the edges incident to ′* that are potentially in ¬* + * are its outgoing 2-colored, its outgoing 3-colored and its outgoing 1-colored edge (Figure 5ii, but ignore the edges marked in yellow). We obtain that deg¬* +* ( ′* ) ≤ 3.
This yields that each degree-4-vertex * in ¬* + * has at least one 1-2-singleton of 2,3 of on its boundary such that * is above and either the outgoing 2-colored edge at or the outgoing 3-colored edge at is on the boundary of and in . We assign each degree-4-vertex to such a 1-2-singleton. Since we never add both the outgoing 2-colored and the outgoing 3-colored edge of a 1-2-singleton to , this assignment is injective. Also, we know that 1 is a 1-2-singleton but as there is no path in covering 1, no degree-4-vertex is assigned to 1. Thus, we obtain that the number of degree-4-vertices in ¬* + * is at most the number of 1-2-singletons minus one. Every 1-2-singleton is incident to a 3-1-colored and a 1-2-colored edge that are both incoming 1-colored. The number of 3-1-colored and a 1-2-colored edges is at most − 3,1 and − 1,2, respectively. Hence, we obtain that the number of degree-4-vertices in ¬* + * is at most min{2,3, − 3,1, − 1,2} − 1.
So far we showed that − is acyclic, ¬* + * has maximum degree at most 4 and that the claimed upper bound on the number of degree-4-vertices of − holds. We now apply the same arguments that we used for to ′ = ¬* ∪ {12, 23, 31} (equality by Lemma 8) and obtain ′. Hence, we have that ′ − ′ is acyclic and + ′* ∖ {12, 23, 31}* has maximum degree at most 4. Since * and * difer on the outer face we obtain the slightly diferent upper bound of min{2′,3, ′ + 2 − ′3,1, ′ + 2 − ′1,2} − 1 for the number of degree-4-vertices of + ′* ∖ {12, 23, 31}* .
The edges 12, 23 and 31 are not in * and there is only one edge on the boundary of the outer face of that is also in . We may thus ignore 12, 23 and 31 and freely switch from ¬* ∪ {12, 23, 31} to ¬* . Hence, we also remove any of the edges 12, 23, 31 from ′. Similar arguments as in [11, proof of Theorem 14] yield that − + ′* and ¬* − ′ + * are both acyclic. As ¬* − ′ + * = ¬( − + ′* )* , this yields that they are also both connected. Hence, they are the desired tree and its co-tree. [2] T. Böhme, J. Harant, M. Kriesell, S. Mohr, J. M. Schmidt, Rooted minors and locally spanning subgraphs, Journal of Graph Theory 105 (2024) 209–229. doi:10.1002/jgt.23012. [3] K. Ota, K. Ozeki, Spanning trees in 3-connected 3,-minor-free graphs, Journal of Combinatorial Theory, Series B 102 (2012) 1179–1188. doi:10.1016/j.jctb.2012.07. 002. [4] K. Ozeki, T. Yamashita, Spanning trees: A survey, Graphs and Combinatorics 27 (2011) 1–26. doi:10.1007/s00373-010-0973-2. [5] D. W. Barnette, 2-connected spanning subgraphs of planar 3-connected graphs, Journal of
Combinatorial Theory, Series B 61 (1994) 210–216. doi:10.1006/jctb.1994.1045. [6] Z. Gao, 2-connected coverings of bounded degree in 3-connected graphs, Journal of Graph
Theory 20 (1995) 327–338. doi:10.1002/jgt.3190200309. [7] T. Biedl, Trees and co-trees with bounded degrees in planar 3-connected graphs, in: 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’14), 2014, pp. 62–73. doi:10.1007/978-3-319-08404-6\_6. [8] Z. Gao, R. B. Richter, 2-Walks in circuit graphs, Journal of Combinatorial Theory, Series B 62 (1994) 259–267. doi:10.1006/jctb.1994.1068. [9] R. Brunet, M. N. Ellingham, Z. Gao, A. Metzlar, R. B. Richter, Spanning planar subgraphs of graphs in the torus and Klein bottle, Journal of Combinatorial Theory, Series B 65 (1995) 7–22. doi:10.1006/jctb.1995.1041. [10] B. Grünbaum, Polytopes, graphs, and complexes, Bulletin of the American Mathematical
Society 76 (1970) 1131–1201. doi:10.1090/S0002-9904-1970-12601-5. [11] C. Ortlieb, J. M. Schmidt, Toward Grünbaum’s Conjecture, in: 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024, pp. 37:1–37:17. doi:10.4230/LIPIcs.SWAT.2024.37. [12] S. Felsner, Geodesic embeddings and planar graphs, Order 20 (2003) 135–150. doi:10.
1023/B:ORDE.0000009251.68514.8b. [13] W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138–148. URL: http://dl.acm. org/citation.cfm?id=320176.320191. [14] S. Felsner, Geometric Graphs and Arrangements, Advanced Lectures in Mathematics,
Vieweg+Teubner, Wiesbaden, 2004. doi:10.1007/978-3-322-80303-0. [15] S. Felsner, Convex drawings of planar graphs and the order dimension of 3-polytopes,
Order 18 (2001) 19–37. doi:10.1023/A:1010604726900. [16] G. Di Battista, R. Tamassia, L. Vismara, Output-sensitive reporting of disjoint paths,
Algorithmica 23 (1999) 302–340. doi:http://dx.doi.org/10.1007/PL00009264. [17] S. Felsner, Lattice structures from planar graphs, Electronic Journal of Combinatorics 11 (2004) R15, 1–24. doi:10.37236/1768. [18] G. Kant, Drawing planar graphs using the canonical ordering, Algorithmica 16 (1996) 4–32. URL: http://dx.doi.org/10.1007/BF02086606. [19] G. Kant, Drawing planar graphs using the lmc-ordering, in: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS’92), 1992, pp. 101–110. doi:10.1109/SFCS.1992.267814. [20] P. O. de Mendez, Orientations bipolaires, Ph.D. thesis, École des Hautes Études en Sciences
Sociales, Paris, 1994. [21] M. Badent, U. Brandes, S. Cornelsen, More canonical ordering, Journal of Graph Algorithms and Applications 15 (2011) 97–126. doi:10.7155/jgaa.00219. [22] M. J. Alam, W. Evans, S. G. Kobourov, S. Pupyrev, J. Toeniskoetter, T. Ueckerdt, Contact representations of graphs in 3D, in: Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS ’15), volume 9214 of Lecture Notes in Computer Science, 2015, pp. 14–27. doi:10.1007/978-3-319-21840-3\_2, technical Report accessible on arXiv: arxiv.org/abs/1501.00304.