Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits

A simple undirected graph G = ( V , E ) is a rigidity circuit if | E | = 2 | V | − 2 and | E G [ X ] | ≤ 2 | X | − 3 for every X ⊂ V with 2 ≤ | X | ≤ | V | − 1 , where E G [ X ] denotes the set of edges connecting vertices in X . It is known that a rigidity circuit can be decomposed into two edge-disjoint spanning trees. Graver et al. (1993) [5] asked if any rigidity circuit with maximum degree 4 can be decomposed into two edge-disjoint Hamiltonian paths. This paper presents infinitely many counterexamples for the question. Counterexamples are constructed based on a new characterization of a 3-connected plane graph in terms of the sparsity of its medial graph and a sufficient condition for the connectivity of medial graphs.