Transversal structures on triangulations: A combinatorial study and straight-line drawings (Q1011766)

The paper deals with irreducible (each 3-cycle is a face boundary) near-triangulations (all faces, except the outer one, have 3 edges) with the outer face quadrangular. A \textit{transversal edge-partition} of such a graph is a partition of the inner edges (not belonging to the outer face) into two classes (colors) red and blue such that: {\parindent=8mm \begin{itemize}\item[C1.]In clockwise order around an inner vertex \(v\) the edges incident to \(v\) alternate in 4 color blocks - RBRB. \item[C2.]If \(v_1\), \(v_2\), \(v_3\), \(v_4\) are the four outer vertices in clockwise order, the inner edges incident to \(v_1\) and \(v_3\) have the same color, and the inner edges incident to \(v_2\) and \(v_4\) have the other color. \end{itemize}} A similar concept - \textit{transversal pair of bipolar orientations} - is defined, as well. The first result states that for a fixed such near-triangulation, the set of transversal edge-partitions is a distributive lattice. The second result establishes a bijection (via the closure mapping) between the set of ternary trees with \(n\) nodes and the set of irreducible near-triangulations with \(n\) inner vertices. The final result provides a straight-line drawing algorithm with grid size asymptotically with high probability \(11n/27 \times 11n/27\) up to an additive error of \(\mathcal O (\sqrt n)\).