Partitions of complete geometric graphs into plane trees (Q2489020)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitions of complete geometric graphs into plane trees |
scientific article |
Statements
Partitions of complete geometric graphs into plane trees (English)
0 references
16 May 2006
0 references
A geometric graph \(G\) is a pair \((V(G),E(G))\) where \(V(G)\) is a set of points in general position (no three are collinear), and \(E(G)\) is a set of closed segments with end points in \(V(G)\). The elements of \(V(G)\) are vertices and the elements of \(E(G)\) are edges. A geometric graph is plane if no two edges cross. A convex graph is a geometric graph with the vertices in convex position. For a tree \(T\) let \(T'\) be the tree obtained by deleting the leaves and leaf edges for \(T\). A caterpillar is a tree \(T\) such that \(T'\) is a path. A tree \(T\) is symmetric if there exists an edge \(vw\) of \(T\) such that if \(A\) and \(B\) are the components of \(T\diagdown vw\) then there exists an isomorphism between \(A\) and \(B\) that map \(v\) to \(w\). The main result of the paper is the following theorem. Let \(T_1,T_2,\dots,T_n\) be a partition of the edges of the convex complete graph \(K_{2n}\) into plane spanning trees. Then \(T_1,T_2,\dots,T_n\) are symmetric convex caterpillars that are pairwise isomorphic. Conversely, for any symmetric convex caterpillar \(T\) on \(2n\) vertices, the edges of the convex complete graph \(K_{2n}\) can be partitioned into \(n\) plane spanning convex copies of \(T\) that are pairwise isomorphic. Moreover, there is proved a sufficient condition which generalizes the convex case for a complete geometric graph \(K_{2n}\) to have a partition into plane spanning double stars that are pairwise isomorphic.
0 references
complete graph
0 references
convex graph
0 references
book embedding
0 references
book thickness
0 references
crossing family
0 references