Connected Dominating Sets in Triangulations

Bose, Prosenjit; Dujmović, Vida; Houdrouge, Hussein; Morin, Pat; Odak, Saeed

doi:10.4230/LIPIcs.ICALP.2026.41

Connected Dominating Sets in Triangulations

Prosenjit Bose

School of Computer Science, Carleton University, Ottawa, Canada Vida Dujmović

School of Computer Science and Electrical Engineering, University of Ottawa, Canada Hussein Houdrouge

School of Computer Science, Carleton University, Ottawa, Canada Pat Morin

School of Computer Science, Carleton University, Ottawa, Canada Saeed Odak

Department of Computer Science, Aalto University, Espoo, Finland

Abstract

A dominating set of a graph $G$ is connected if it induces a connected graph in $G$ . For planar triangulations, it has been known since 1990 that every $n$ -vertex triangulation admits a connected dominating set of size at most $n/2-1$ , and no improvement to this bound was known for over three decades. We break this longstanding barrier by showing that every $n$ -vertex triangulation has a connected dominating set of size at most $10n/21$ . Equivalently, every triangulation admits a spanning tree with at least $11n/21$ leaves. Moreover, we present an algorithm that computes such a set in optimal linear time. Our result narrows the gap to the best known lower bound and has graph drawing applications, establishing a bound for one-bend free sets and improving the known bound for simultaneous planar embeddings.

Keywords and phrases:

connected domination, triangulations, planar graphs, graph drawing, collinear sets

Category:

Track A: Algorithms, Complexity and Games

Funding:

Prosenjit Bose: Research partially funded by NSERC.

Vida Dujmović: Research partially funded by NSERC and a University of Ottawa Research Chair.

Hussein Houdrouge: Research partially funded by NSERC.

Pat Morin: Research partially funded by NSERC.

Copyright and License:

2012 ACM Subject Classification:

Human-centered computing

\rightarrow

Graph drawings ; Theory of computation

\rightarrow

Computational geometry ; Mathematics of computing

\rightarrow

Graph algorithms

DOI:

10.4230/LIPIcs.ICALP.2026.41

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A set $X$ of vertices in a graph $G$ is a dominating set of $G$ if each vertex of $G$ is in $X$ or adjacent to a vertex in $X$ .¹¹1Any graph $G$ that we consider in this paper is a finite undirected graph without self-loops and without parallel edges, with vertex set $V(G)$ and edge set $E(G)$ . A dominating set $X$ of $G$ is connected if the subgraph $G[X]$ of $G$ induced by the vertices in $X$ is connected. There is an enormous body of literature on dominating sets. Several books are devoted to the topic [24, 23, 14, 22], including a book and book chapter devoted to connected dominating sets [14],[24, Chapter 4]. Connected dominating sets have numerous applications, particularly in areas such as wireless ad hoc networks, as well as broadcasting and multi-casting; see, for example [32].

A typical result in the area is an upper bound of the form: “Every $n$ -vertex graph in some family $\mathcal{G}$ of graphs has a (connected) dominating set of size at most $f(n)$ .” or a lower bound of the form “For infinitely many $n$ , there exists an $n$ -vertex member of $\mathcal{G}$ with no (connected) dominating set of size less than $g(n)$ .”

One family of graphs that has received considerable attention in this context is the class of triangulations, that is, edge-maximal planar graphs. Matheson and Tarjan [29] proved that every $n$ -vertex triangulation has a dominating set of size at most $n/3=0.33\overline{3}n$ and that there exists $n$ -vertex triangulations with no dominating set of size less than $n/4=0.25n$ . The gap between these upper and lower bounds stood for over $20$ years until a recent breakthrough reduced the upper bound to $17n/53\approx 0.32075471698n$ [33]. This was swiftly followed by an improvement to $2n/7=0.2\overline{857142}n$ [10].

The focus of the current paper is on the existence of small connected dominating sets in triangulations. In the following sections, we describe the history of this problem and then present our main results. At the end of the paper we present corollaries of our results for two applications in graph drawing.

Connected dominating sets are complementary to the leaves of spanning trees in the following sense: a set of vertices $X$ is a connected dominating set of an $n$ -vertex graph $G$ if and only if $G$ has a spanning tree in which the vertices of $G-X$ are all leaves in $G$ . Thus, connected dominating sets are studied implicitly in the literature on spanning trees with many leaves [13, 28, 3, 4, 6, 30]. A closely related and extensively studied notion is that of spanning trees with no degree two vertices, known as homeomorphically irreducible spanning trees [8, 1, 9, 26, 25, 20]. Since an $n$ -vertex tree with no degree $2$ -vertices has at least $n/2+1$ leaves, the existence of a homeomorphically irreducible spanning tree implies the existence of a spanning tree with at least $n/2+1$ leaves (and the existence of a connected dominating set of size at most $n/2-1$ ). As stated already, we consider connected dominating sets in triangulations. An easy consequence of the proof in [29] is that $n$ -vertex triangulations have connected dominating sets of size at most $2n/3=0.66\overline{6}n$ . A more general result [28] shows that graphs of minimum-degree $3$ in which each edge is included in a $3$ -cycle have connected dominating sets of size at most $2(n-5)/3<0.66\overline{6}n$ . Albertson et al [1] prove that every triangulation has a homeomorphically irreducible spanning tree which, as discussed above, implies that every triangulation has a connected dominating set of size at most $n/2-1<0.5n$ .

Chen et al [8] give a significant generalization of this result, which applies to any connected graph $G$ in which the graph induced by the neighbours of each vertex is connected. Answering an open problem by [1] and confirming the conjecture of Archdeacon [21], the work in [9] generalizes this result to graphs in which every edge is in at least two $3$ -cycles.

Motivated by the fact that the $0.5n$ upper bound for triangulations has stood for over three decades, several authors have asked if it can be improved. Bradshaw et al [7, Question 4.2] ask if it can be improved to $n/3$ . As it turns out, the answer is negative (see below for more on the lower bound). Noguchi and Zamfirescu [30] posed an even more modest question, asking whether the bound could be improved to $(\tfrac{1}{2}-\epsilon)n$ for some $\epsilon>0$ , even when restricted to the special case of $4$ -connected triangulations.

Our main contribution is the first improvement to the longstanding $n/2$ upper bound for connected dominating sets in triangulations, as stated in the following theorem.

Theorem 1.

For every $n\geq 3$ , every $n$ -vertex triangulation $G$ has a connected dominating set $X$ of size at most $10n/21=0.\overline{476190}n$ . Equivalently, $G$ has a spanning tree $T$ with at least $11n/21=0.\overline{523809}n$ leaves. Furthermore, there exists an $O(n)$ time algorithm for finding $X$ and $T$ .

Until recently, the best known lower bound for this problem, illustrated in Figure 1, was $n/3=0.33\overline{3}n$ , obtained from a triangulation that contains $n/3$ vertex-disjoint pairwise-nested triangles $\Delta_{1},\ldots,\Delta_{n/3}$ . In order to dominate $\Delta_{1}\cup\Delta_{2}$ , any connected dominating set must contain at least two vertices in $\Delta_{1}\cup\Delta_{2}$ . In order to dominate $\Delta_{n/3-1}\cup\Delta_{n/3}$ , any connected dominating set must contain at least two vertices in $\Delta_{n/3-1}\cup\Delta_{n/3}$ . Then, in order to be connected, any connected dominating set must contain a vertex in each of $\Delta_{3},\ldots,\Delta_{n/3-2}$ .

Figure 1: A triangulation with

n=3k

vertices whose smallest connected dominating set has size

n/3

.

Since this example contains many separating triangles it is natural to consider the special case of $4$ -connected triangulations. Noguchi and Zamfirescu [30] describe, for infinitely many values of $n$ , $4$ -connected $n$ -vertex triangulations for which any connected dominating set has at least $n/3$ vertices. Very recently, the $n/3$ lower bound has been improved to $\frac{7}{18}n-\frac{2}{3}$ by Enami et al [19].

1.1 Outline

The remainder of this paper is organized as follows: In Section 2, we describe the general strategy we use for finding connected dominating sets in triangulations. In Section 2.2 we show that a simple version of this strategy can be used to obtain a connected dominating set of size at most $4n/7=0.\overline{571428}n$ . In Section 3 we show that a more careful construction leads to a proof of Theorem 1. In Section 4, we discuss the connection between connected dominating sets and a graph drawing application. Finally, Section 5 concludes by pointing out directions for future work.

2 The General Strategy

Throughout this paper, we use standard graph-theoretic terminology as used, for example, by [12]. For a graph $G$ , let $|G|=|V(G)|$ denote the number of vertices of $G$ . A bridge in a graph $G$ is an edge $e$ of $G$ such that $G-e$ has more connected components than $G$ . For a vertex $v\in G$ , $N_{G}(v):=\{w\in V(G):vw\in E(G)\}$ is the open neighbourhood of $v$ in $G$ , $N_{G}[v]:=N_{G}(v)\cup\{v\}$ is the closed neighbourhood of $v$ in $G$ . For a vertex subset $S\subseteq V(G)$ , $N_{G}[S]:=\bigcup_{v\in S}N_{G}[v]$ is the closed neighbourhood of $S$ in $G$ and $N_{G}(S):=N_{G}[S]\setminus S$ is the open neighbourhood of $S$ in $G$ . A set $X\subseteq V(G)$ dominates a set $B\subseteq V(G)$ if $B\subseteq N_{G}[X]$ . Thus, $X$ is a dominating set of $G$ if and only if $X$ dominates $V(G)$ .

A plane graph is a graph equipped with a non-crossing embedding in $\mathbb{R}^{2}$ . A plane graph is outerplane if all its vertices appear on the outer face. A triangle is a cycle of length $3$ . A near-triangulation is a plane graph whose outer face is bounded by a cycle and whose inner faces are all bounded by triangles. A generalized near-triangulation is a plane graph whose inner faces are bounded by triangles. Note that a generalized near triangulation may have multiple components, cut vertices, and bridges.

In several places we will make use of the following observation, which is really a statement about the triangulation contained in a cycle of length $3$ .

Observation 1.

Let $H$ be a generalized near-triangulation and let $x y z$ be a cycle in $H$ . Then,

1.

If the interior of $x y z$ contains at least one vertex of $H$ , then each of $x$ , $y$ , and $z$ has at least one neighbour in the interior of $x y z$ .
2.

If the interior of $x y z$ contains at least two vertices of $H$ , then at least two of $x$ , $y$ , and $z$ have at least two neighbours in the interior of $x y z$ .

For a plane graph $H$ , we use the notation $B(H)$ to denote the vertex set of the outer face of $H$ and define $I(H):=V(H)\setminus B(H)$ . The vertices in $B(H)$ are boundary vertices of $H$ and the vertices in $I(H)$ are inner vertices of $H$ . For any vertex $v$ of $H$ , the inner neighbourhood of $v$ in $H$ is defined as $N_{H}^{+}(v):=N_{H}(v)\cap I(H)$ , the vertices in $N^{+}_{H}(v)$ are inner neighbours of $v$ in $H$ , and $\deg^{+}_{H}(v)=|N^{+}_{H}(v)|$ is the inner-degree of $v$ in $H$ .

Let $G$ be a triangulation. Our procedure for constructing a connected dominating set $X$ begins with an incremental phase that eats away at $G$ “from the outside.” The process of constructing $X$ is captured by the following definition: A vertex subset $X\subseteq V(G)$ is outer-domatic if it can be partitioned into non-empty subsets $\Delta_{0},\Delta_{1},\ldots,\Delta_{r-1}$ such that

(P1)

$\Delta_{0}\subseteq B(G)$ ;
(P2)

$\Delta_{i}\subseteq B(G-(\bigcup_{j=0}^{i-1}\Delta_{j}))$ for each $i\in\{1,\ldots,r-1\}$ ; and
(P3)

$G-(\bigcup_{j=0}^{r-1}\Delta_{j})$ is outerplane.

Lemma 1.

Let $G$ be a triangulation. Then any outer-domatic $X\subseteq V(G)$ is a connected dominating set of $G$ .

We will present two algorithms that grow a connected dominating set in small batches $\Delta_{0},\Delta_{1},\ldots,\Delta_{r-2}$ that result in a sequence of sets $X_{1},\ldots,X_{r-1}$ where $X_{i}=\bigcup_{j=0}^{i-1}\Delta_{j}$ . Each of these algorithms is unable to continue once they reach a point where each vertex in $B(G-X_{i})$ has inner-degree at most $1$ in $G-X_{i}$ . We begin by studying the graphs that cause this to happen.

2.1 Critical Graphs

A generalized near-triangulation $H$ is critical if $\deg^{+}_{H}(v)\leq 1$ for each $v\in B(H)$ . We say that an inner face of $H[B(H)]$ is marked if it contains an inner vertex of $H$ .

Figure 2: Some critical graphs

H

with the marked faces of

H[B(H)]

shaded.

Lemma 2.

Let $H$ be a critical generalized near-triangulation. Then each face $f$ of $H[B(H)]$ contains at most one vertex of $I(H)$ and this vertex is adjacent to every vertex of $f$ .

Lemma 3.

Let $H$ be a critical generalized near-triangulation. Then $|B(H)|\geq 3|I(H)|$ and there exists $\Delta\subseteq B(H)$ of size at most $|I(H)|$ that dominates $I(H)$ .

2.2 A Simple Algorithm

We start with the simplest possible greedy algorithm, that we call $\textsc{SimpleGreedy}(G)$ , to choose $\Delta_{0},\ldots,\Delta_{r-1}$ . Suppose we have already chosen $\Delta_{0},\ldots,\Delta_{i-1}$ for some $i\geq 0$ and we now want to choose $\Delta_{i}$ . For $i\geq 0$ , we let $X_{i}:=\bigcup_{j=0}^{i-1}\Delta_{j}$ , let $G_{i}:=G-X_{i}$ , and let $v_{i}$ be a vertex in $B(G_{i})$ that maximizes $\deg^{+}_{G_{i}}(v_{i})$ . During iteration $i\geq 0$ , there are only two cases to consider:

[g1]

If $\deg^{+}_{G_{i}}(v_{i})\geq 2$ then we set $\Delta_{i}:=\{v_{i}\}$ .
[g2]

If $\deg^{+}_{G_{i}}(v_{i})\leq 1$ then $G_{i}$ is critical and this is the final step, so $r:=i+1$ . By Lemma 3, there exists $\Delta_{i}\subseteq B(G_{i})$ of size at most $|I(G_{i})|$ that dominates $I(G_{i})$ . Then $X_{r}:=X_{r-1}\cup\Delta_{i}$ and we are done.

Theorem 2.

When applied to an $n$ -vertex triangulation $G$ , $\textsc{SimpleGreedy}(G)$ produces a connected dominating set $X_{r}$ of size at most $(4n-9)/7$ .

Proof.

By the choice of $\Delta_{0},\ldots,\Delta_{r-1}$ , $X_{r}$ is an outer-domatic subset of $V(G)$ so, by Lemma 1, $X_{r}$ is a connected dominating set of $G$ . All that remains is to analyze the size of $X_{r}$ . For each $i\in\{1,\ldots,r\}$ , let $D_{i}:=N_{G}[X_{i}]$ be the subset of $V(G)$ that is dominated by $X_{i}$ , let $I_{i}:=V(G)\setminus D_{i}$ be the subset of $V(G)$ not dominated by $X_{i}$ , and let $B_{i}:=N_{G}(I_{i})$ be the vertices of $G$ that have at least one neighbour in each of $X_{i}$ and $I_{i}$ . We use the convention that $D_{0}:=B(G)$ .

First observe that, for $i\in\{0,\ldots,r-2\}$ , $|D_{i+1}|\geq|D_{i}|+\deg_{G_{i}}^{+}(v_{i})$ since $D_{i+1}\supseteq D_{i}$ and $D_{i+1}$ contains the $\deg_{G_{i}}^{+}(v_{i})$ inner neighbours of $v_{i}$ in $G_{i}$ . Therefore

|D_{r-1}|\geq|D_{0}|+\sum_{i=0}^{r-2}\deg_{G_{i}}^{+}(v_{i})\geq 3+\sum_{i=0}^% {r-2}2=2r+1\enspace.

Since $D_{r-1}$ and $I_{r-1}$ partition $V(G)$ ,

n=|D_{r-1}|+|I_{r-1}|\geq 2r+1+|I_{r-1}|\enspace.

(1)

Since $X_{r-1}$ and $B_{r-1}$ are disjoint and $D_{r-1}\supseteq B_{r-1}\cup X_{r-1}$ , we have $|D_{r-1}|\geq|X_{r-1}|+|B_{r-1}|=r-1+|B_{r-1}|$ . Therefore,

\displaystyle n

\displaystyle=|D_{r-1}|+|I_{r-1}|\geq r-1+|B_{r-1}|+|I_{r-1}|\geq r-1+4|I_{r-1% }|\enspace,

(2)

where the last inequality follows from Lemma 3.

The final dominating set $X_{r}$ has size $|X_{r}|=|X_{r-1}|+\Delta_{r-1}=r-1+|I_{r-1}|$ , so the size of $|X_{r}|$ can be upper-bounded by maximizing $r-1+|I_{r-1}|$ subject to Equations 1 and 2. More precisely, by setting $x:=r$ and $y:=|I_{r-1}|$ , the maximum size of $X_{r}$ is upper-bounded by the maximum value of $x-1+y$ subject to the constraints

	$\displaystyle x,y\geq 0$
	$\displaystyle x-1+4y$	$\displaystyle\leq n$
	$\displaystyle 2x+1+y$	$\displaystyle\leq n$

This is an easy linear programming exercise and the maximum value of $X_{r}$ is obtained when $r=(3n-5)/7$ and $|I_{r-1}|=(n+3)/7$ , which gives $|X_{r}|\leq(4n-9)/7$ . $\hfill\blacktriangleleft$

3 A Better Algorithm: Proof of Theorem 1

Next we devise an algorithm that produces a smaller connected dominating set than what $\textsc{SimpleGreedy}(G)$ can guarantee. This involves a more careful analysis of the cases in which SimpleGreedy is forced to take a vertex $v_{i}$ with $\deg^{+}_{G_{i}}(v_{i})=2$ . We will show that in most cases, any time the algorithm is forced to choose a vertex $v$ that has inner-degree $2$ in $G_{i}$ , this can immediately be followed by choosing a vertex $w$ that has inner-degree at least $3$ in $G_{i}-v$ . This is explained in Section 3.2.

When this is no longer possible, the algorithm will be forced to directly handle a graph $G_{i}$ in which $\deg^{+}_{G_{i}}(v)\leq 2$ for all $v\in B(G_{i})$ and $G_{i}-(B_{i})$ is critical. In Section 3.5 we explain how this can be done using a set $X_{r-1}$ whose size depends only on $G_{i}-B(G_{i})$ . The results in Section 3.5 require that the graph $G_{i}-B(G_{i})$ not have any vertices of degree less than $2$ . The steps required to eliminate degree- $1$ and degree- $0$ vertices from $G_{i}-B(G_{i})$ are explained in Sections 3.4 and 3.3.

3.1 Dom-Minimal Dom-Respecting Graphs

We begin by identifying unnecessary vertices and edges that can appear in the graphs $G_{1},\ldots,G_{r-1}$ during the construction of $X$ . Refer to Figure 3. We say that a near-triangulation $H$ is dom-minimal if

(DM1)

each vertex $v\in B(H)$ has $\deg^{+}_{H}(v)\geq 1$ ;
(DM2)

for each $v\in B(H)$ with $\deg^{+}_{H}(v)=1$ , $H[N_{H}[v]]$ is isomorphic to $K_{4}$ ; and
(DM3)

each edge $v w$ on the boundary of the outer face of $H$ is also on the boundary of some inner face $v w x$ of $H$ , where $x\in I(H)$ .

We say that a generalized near-triangulation $H$ is dom-minimal if each of its biconnected components²²2A biconnected component of a graph $G$ is a 2-connected maximal sub-graph. In other words, removing a vertex from this component keeps it connected. is dom-minimal.

Figure 3: A generalized near-triangulation that is not dom-minimal. The red vertices violate Item 1, the green vertex violates Item 2, and the red edges violate Item 3.

Observation 2.

Any dom-minimal generalized near-triangulation $H$ is bridgeless.

Let $H$ and $H^{\prime}$ be two generalized near-triangulations. We say that $H^{\prime}$ dom-respects $H$ if

(DP1)

$B(H^{\prime})\subseteq B(H)$ ;
(DP2)

$I(H^{\prime})=I(H)$ ; and
(DP3)

$N_{H^{\prime}}(v)\cap I(H)\subseteq N_{H}(v)\cap I(H)$ for all $v\in V(H^{\prime})$ .

Observation 3.

Let $H$ and $H^{\prime}$ be generalized near-triangulations where $H^{\prime}$ dom-respects $H$ and let $\Delta^{\prime}$ be a subset of $V(H^{\prime})$ that dominates $I(H^{\prime})$ in $H^{\prime}$ . Then $\Delta^{\prime}$ dominates $I(H)$ in $H$ .

Lemma 4.

For any generalized near-triangulation $H$ , there exists a dom-minimal generalized near-triangulation $H^{\prime}$ that dom-respects $H$ .

Proof.

The proof is by induction on $|V(H)|+|E(H)|$ . If $H$ is already dom-minimal, then setting $H^{\prime}=H$ satisfies the requirements of the lemma, so assume that $H$ is not dom-minimal. Since Items 1, 2, and 3 are transitive relations, the dom-respecting relation is transitive: If $H^{\prime}$ dom-respects $H^{*}$ and $H^{*}$ dom-respects $H$ , then $H^{\prime}$ dom-respects $H$ . Therefore, it is sufficient to find $H^{*}$ with fewer edges or fewer vertices than $H$ that dom-respects $H$ , and the inductive hypothesis provides the desired dom-minimal graph $H^{\prime}$ that dom-respects $H^{*}$ and $H$ .

If $H$ contains a vertex $v\in B(H)$ with $\deg^{+}_{H}(v)=0$ then $H-v$ is a generalized near-triangulation, $B(H-v)\subset B(H)$ , $I(H-v)=I(H)$ , and $N_{H-v}(v)\cap I(H)=N_{H}(v)\cap I(H)$ for all $v\in V(H-v)$ . Therefore $H-v$ dom-respects $H$ and has fewer vertices than $H$ so we can apply the inductive hypothesis and be done. We now assume that $\deg^{+}_{H}(v)\geq 1$ for all $v\in B(H)$ . Since $H$ is not dom-minimal, $H$ contains a biconnected component $C$ that is not dom-minimal. If $|C|=2$ then $C$ contains a single edge (a bridge of $H$ ) and removing this edge from $H$ produces a graph with fewer edges that dom-respects $H$ . Therefore, $C$ has at least three vertices. (See Figure 4.)


$\Downarrow$	$\Downarrow$	$\Downarrow$

Figure 4: Three cases on the way to making

H

dom-minimal.

1.

Item 3: If there exists an edge $v w$ on the outer face of $C$ that is not incident to any inner face $v w x$ with $x\in I(C)$ then $H-vw$ is a generalized near-triangulation, $B(H-vw)=B(H)$ , and $I(H-vw)=I(H)$ , and $N_{H-vw}(v)\cap I(H)=N_{H}(v)\cap I(H)$ for all $v\in V(H-vw)$ . Therefore, $H-vw$ dom-respects $H$ and has few edges than $H$ . (This includes the case where $C$ consists of the single edge $v w$ .)
2.

Item 1: If there exists a vertex $v\in B(C)$ with $\deg^{+}_{C}(v)=0$ then $v$ is incident to an edge $v w$ that is on the outer face of $C$ and on the outer face of $H$ . Since $\deg^{+}_{C}(v)=0$ , $v w$ is not incident to any inner face $v w x$ with $x\in I(C)$ and we can proceed as in the previous case. (This eventually leads to all edges of $C$ incident to $v$ being removed from $H$ .)
3.

Item 2: If there exists a vertex $v\in B(C)$ with $\deg^{+}_{C}(v)=1$ then $H$ contains faces $x v w$ and $v y w$ where $w$ is an inner vertex. If Case 1 does not apply to either of the two edges on the outer face of $C$ incident to $v$ then $x$ and $y$ are on the outer face of $C$ . If $H[N_{C}[v]]$ is not isomorphic to $K_{4}$ , then $xy\not\in E(H)$ . In this case, let $H^{\star}$ be the graph obtained from $H$ by removing the edge $v w$ and replacing the edges $x v$ and $v y$ with the edge $x y$ . Then $H^{\star}$ is a generalized near-triangulation, $B(H^{*})=B(H)$ , $I(H^{*})=I(H)$ , and $N_{H^{*}}(v)\cap I(H)\subseteq N_{H}(v)\cap I(H)$ . Therefore $H^{\star}$ dom-respects $H$ and has fewer edges than $H$ .

$\hfill\blacktriangleleft$

3.2 Finding a $2$ – $3$ Combo

Next, we show that in most cases our algorithm for constructing a connected dominating set is not forced to choose a single vertex of inner-degree $2$ . Instead, it can choose a pair $v, w$ such that $\deg^{+}_{H}(v)=2$ and $\deg^{+}_{H-v}(w)\geq 3$ . Note that the next two lemmas each consider a graph $H$ that is a near-triangulation, not a generalized near-triangulation.

Lemma 5.

Let $H$ be a dom-minimal near-triangulation and let $v_{0}$ be a vertex in $B(H)$ with $|N_{H}(v_{0})\cap B(H)|\geq 3$ . Then $\deg^{+}_{H}(v_{0})\geq 2$ . In other words, if $v_{0}$ is incident to a chord of the outerplane graph $H[B(H)]$ , then $v_{0}$ is incident to at least two inner vertices of $H$ .

Figure 5: The proof of Lemma 5.

Lemma 6.

Let $H$ be a dom-minimal near-triangulation. Then either:

1.

$H$ is isomorphic to $K_{4}$ ;
2.

each vertex $w\in B(H-B(H))$ has a neighbour $v$ in $B(H)$ with $\deg^{+}_{H}(v)\geq 2$ .

Note that the next three lemmas consider the case where $H$ is a generalized near-triangulation. The following lemma is illustrated in Figure 6.

Figure 6: Removing an inner-degree

2

vertex

v

is immediately followed by removing an inner-degree

3

vertex

w

and the vertex

u

is not in a dom-minimal graph that dom-respects

H-\{v,w\}

.

Lemma 7.

Let $H$ be a dom-minimal generalized near-triangulation. Then either:

(1)

$H-B(H)$ is critical;
(2)

$B(H)$ contains a vertex $v$ with $\deg^{+}_{H}(v)\geq 3$ ; or
(3)
$H$ contains distinct vertices $v_{0}$ , $v_{j}$ , and $w$ such that
1. (a)
  
  $v_{0}\in B(H)$ and $\deg^{+}_{H}(v_{0})=2$ ;
2. (b)
  
  $w\in B(H-v_{0})$ and $\deg^{+}_{H-v_{0}}(w)\geq 3$ ; and
3. (c)
  
  $v_{j}\in B(H)$ and $N^{+}_{H}(v_{j})\subseteq N_{H}[w]$ .

Figure 7: The proof of Lemma 7.

The following is a restatement of Lemma 7 in language that is more useful in the description of an algorithm for constructing a connected dominating set.

Corollary 1.

Let $H$ be a dom-minimal generalized near-triangulation. Then either:

(1)

$H-B(H)$ is critical;
(2)

there is a vertex $v\in B(H)$ and a dom-respecting subgraph $H^{\prime}$ of $H-v$ with $|H^{\prime}|\leq|H|-1$ and $|B(H^{\prime})|\geq|B(H)|+2$ ; or
(3)

there is an edge $vw\in E(H)$ with $v\in B(H)$ , $w\in B(H-B(H))$ , and a dom-respecting subgraph $H^{\prime}$ of $H-\{v,w\}$ with $|H^{\prime}|=|H|-3$ and $|B(H^{\prime})|=|B(H)|+2$ .

3.3 Eliminating Inner Leaves

Next we show that, even when all vertices in $B(H)$ have inner-degree at most $2$ and $H-B(H)$ is critical, we can still efficiently dominate any vertex that has degree $1$ in $H-B(H)$ .

Lemma 8.

Let $H$ be a dom-minimal generalized near-triangulation such that $\deg^{+}_{H}(v)\leq 2$ for all $v\in B(H)$ , $H-B(H)$ is critical, and $H-B(H)$ contains a vertex $w$ with $\deg_{H-B(H)}(w)=1$ . Then there exists $v\in B(H)$ and a dom-respecting subgraph $H^{\prime}$ of $H-v$ such that $|H^{\prime}|\leq|H|-3$ and $|B(H^{\prime})|\leq|B(H)|-1$ .


$H$	$H-v$	$H^{\prime}$

Figure 8: The proof of Lemma 8.

3.4 Eliminating Inner Isolated Vertices

We now show that, even when all vertices in $B(H)$ have inner-degree at most $2$ , $H-B(H)$ is critical, and $H-B(H)$ has no degree- $1$ vertices, we can still efficiently dominate degree- $0$ vertices in $H-B(H)$ .

Lemma 9.

Let $H$ be a dom-minimal generalized near-triangulation such that $\deg^{+}_{H}(v)\leq 2$ for all $v\in B(H)$ , $H-B(H)$ is critical, and $H-B(H)$ contains a vertex $w$ with $\deg_{H-B(H)}(w)=0$ but does not contain any vertex $w^{\prime}$ with $\deg_{H-B(H)}(w^{\prime})=1$ . Then there exists $v\in B(H)$ and a graph $H^{\prime}$ that dom-respects $H-v$ such that $|H^{\prime}|\leq|H|-3$ and $|B(H^{\prime})|\leq|B(H)|-1$ .

Proof.

Refer to Figure 9 for an idea of the proof. $\hfill\blacktriangleleft$

(i)	(ii)	(iii)

$\Downarrow$	$\Downarrow$	$\Downarrow$

$\Downarrow$	$\Downarrow$	$\Downarrow$

Figure 9: Eliminating isolated vertices in

H-B(H)

.

3.5 $2$ -Critical Graphs

We now explain what the algorithm does when it finally reaches a state where none of Corollary 1, Lemma 8 or Lemma 9 can be used to make an incremental step. The inapplicability of Lemmata 8, 9, and 1 leads to the following definition: A generalized near-triangulation $H$ is $2$ -critical if

(2-C1)

$\deg^{+}_{H}(v)\leq 2$ for each $v\in B(H)$ ;
(2-C2)

$H-B(H)$ is critical; and
(2-C3)

$\deg_{H-B(H)}(w)\geq 2$ for all $w\in V(H-B(H))$ .

(See Figure 10.) We will work our way up to a proof of the following lemma, which allows our algorithm to handle $2$ -critical graphs directly, in one step:

Figure 10: A

2

-critical generalized near-triangulation.

Lemma 10.

Let $H$ be a $2$ -critical generalized near-triangulation. Then there exists $X\subseteq V(H)$ of size at most $(2|B(H-B(H))|+I(H-B(H)))/3$ that dominates $I(H)$ and such that each component of $H[X]$ contains at least one vertex in $B(H)$ .

Lemma 11.

Let $H$ be a dom-minimal $2$ -critical generalized near-triangulation. Then $\deg^{+}_{H}(v)=2$ for all $v\in B(H)$ .

Lemma 12.

Let $H$ be a dom-minimal $2$ -critical generalized near-triangulation. Then $|B(H)|\geq|B(H-B(H))|$ .

For each integer $r\geq 3$ , the $r$ -wheel $W_{r}$ is the near-triangulation whose outer face is bounded by a cycle $v_{0},\ldots,v_{r-1}$ that contains a single vertex $x$ in its interior and that is adjacent to each of $v_{0},\ldots,v_{r-1}$ . For even values of $r$ , $W_{r}$ is called an even wheel. Note that the following lemma, illustrated in Figure 11 is about critical graphs, not $2$ -critical graphs.

Figure 11: Lemma 13: Partitioning the vertices of a biconnected critical graph into three dominating sets.

Lemma 13.

Let $H$ be a biconnected critical generalized near-triangulation with at least $3$ vertices and not isomorphic to $W_{k}$ for any even integer $k$ . Then there exists a partition $\{X_{0},X_{1},X_{2}\}$ of $V(H)$ such that

(i)

For each edge $v w$ of $H[B(H)]$ , $v\in X_{i}$ and $w\in X_{j}$ for some $i\neq j$ ;
(ii)

for each $i\in\{0,1,2\}$ , $X_{i}$ dominates $H$ .


$H$	$H^{\prime}$	$H$

Figure 12: The proof of Lemma 13.

The following lemma, illustrated in Figure 13 explains how we deal with even wheels not covered by Lemma 13:

Lemma 14.

Let $H:=W_{k}$ for some even integer $k\geq 4$ and let $v$ be any vertex in $B(H)$ . Then there exists a partition $\{X_{0},X_{1},X_{2}\}$ of $V(H)$ such that

(i)

For each edge $v w$ of $H[B(H)]$ , $v\in X_{i}$ and $w\in X_{j}$ for some $i\neq j$ ;
(ii)

$X_{0}$ dominates $V(H)\setminus\{v\}$ and $X_{1}$ and $X_{2}$ each dominate $H$ .

Figure 13: Lemma 14: Partitioning the vertices of an even wheel into sets

X_{0}

,

X_{1}

, and

X_{2}

.

The following lemma, illustrated in Figure 14, drops the requirement that the critical graph be biconnected and applies even if some of the biconnected components of $H$ are even wheels.

Figure 14: Lemma 15: Partitioning the vertices of a connected critical graph into dominating sets

X_{0}

,

X_{1}

, and

X_{2}

.

Lemma 15.

Let $H$ be a connected critical generalized near-triangulation with at least $3$ vertices, no vertices of degree $1$ and not isomorphic to $W_{k}$ for any even integer $k$ . Then there exists a partition $\{X_{0},X_{1},X_{2}\}$ of $V(H)$ such that

(i)

for each edge $v w$ of $H[B(H)]$ , $v\in X_{i}$ and $w\in X_{j}$ for some $i\neq j$ ;
(ii)

for each $i\in\{0,1,2\}$ , $X_{i}$ dominates $H$ ,

Proof.

The proof is by induction on $|H|$ . First, suppose that $|H|=3$ . Since $H$ is connected and has no vertices of degree $1$ , $H$ is a triangle $v_{0}v_{1}v_{2}$ . We take $X_{i}:=\{v_{i}\}$ for each $i\in\{0,1,2\}$ . Clearly these sets satisfy the requirements of the lemma.

If $H$ is biconnected then, since $H$ is not an even wheel, we can immediately apply Lemma 13 and we are done. Otherwise, $H$ contains a cut vertex $v$ that separates $H$ into components $C_{1},\ldots,C_{k}$ and such that $H^{\prime}:=H[V(C_{1})\cup\{v\}]$ is biconnected. Refer to Figure 15. Since $H$ has no vertices of degree $1$ , $H^{\prime}$ has at least three vertices. If $H^{\prime}$ is isomorphic to $W_{k}$ for some even integer $k$ then we apply Lemma 14 to $H^{\prime}$ and $v$ to obtain sets $X_{0}^{\prime}$ , $X_{1}^{\prime}$ , and $X_{2}^{\prime}$ . Otherwise, we apply Lemma 13 to $H^{\prime}$ to obtain sets $X_{0}^{\prime}$ , $X_{1}^{\prime}$ , and $X_{2}^{\prime}$ . In either case we may assume, without loss of generality that $v\in X_{1}^{\prime}$ , that $X_{1}^{\prime}$ and $X_{2}^{\prime}$ each dominate $H^{\prime}$ and that $X_{0}^{\prime}$ dominates $V(H^{\prime})\setminus\{v\}$ .

Figure 15: Two cases in the proof of Lemma 15.

Let $H^{\prime\prime}:=H-V(C_{1})$ . First, suppose that $\deg_{H^{\prime\prime}}(v)>1$ . If $H^{\prime\prime}$ is isomorphic to $W_{k}$ for some even integer $k$ then we apply Lemma 14 to $H^{\prime\prime}$ and $v$ to obtain sets $X_{0}^{\prime\prime}$ , $X_{1}^{\prime\prime}$ , $X_{2}^{\prime\prime}$ . Otherwise, we apply the inductive hypothesis to $H^{\prime\prime}$ to obtain sets $X_{0}^{\prime\prime}$ , $X_{1}^{\prime\prime}$ , $X_{2}^{\prime\prime}$ that each dominate $H^{\prime\prime}$ . In either case we may assume, without loss of generality (by renaming) that $v\in X_{1}^{\prime\prime}$ , that $X_{1}^{\prime\prime}$ and $X_{2}^{\prime\prime}$ each dominate $H^{\prime}$ and that $X_{0}^{\prime\prime}$ dominates $V(H^{\prime\prime})\setminus\{v\}$ . Then the sets $X_{0}:=X_{0}^{\prime}\cup X_{2}^{\prime\prime}$ , $X_{1}:=X_{1}^{\prime}\cup X_{1}^{\prime\prime}$ and $X_{2}:=X_{2}^{\prime}\cup X_{0}^{\prime\prime}$ satisfy the requirements of the lemma. (The only concern is whether each set dominates $v$ , but this is guaranteed by the fact that $v\in X_{1}$ , and that $X_{2}^{\prime}\subseteq X_{2}$ and $X_{2}^{\prime\prime}\subseteq X_{0}$ each dominate $v$ .)

Finally, if $\deg_{H^{\prime\prime}}(v)=1$ then we consider the maximal path $v,v_{1},v_{2},\ldots,v_{r-1},v_{r}$ such that $\deg_{H^{\prime\prime}}(v_{i})=2$ for each $i\in\{1,\ldots,r-1\}$ . Let $H^{\prime\prime\prime}:=H^{\prime\prime}-\{v,v_{1},\ldots,v_{r-1}\}$ and we treat $H^{\prime\prime\prime}$ exactly as we treated $H^{\prime\prime}$ in the previous paragraph to obtain sets $X_{0}^{\prime\prime\prime}$ , $X_{1}^{\prime\prime\prime}$ and $X_{2}^{\prime\prime\prime}$ . Without loss of generality, we assume that $v_{r}\in X_{(r-1)\bmod 3}$ , that $X_{(r-1)\bmod 3}$ and $X_{(r\bmod 3)}$ each dominate $H^{\prime\prime\prime}$ and that $X_{(r-2)\bmod 3}$ dominates $V(H^{\prime\prime\prime})\setminus\{v_{r}\}$ . Let $X_{0}^{\prime\prime}:=X_{0}^{\prime\prime\prime}\cup\{v_{i}:i\equiv 2\pmod{3}\}$ , $X_{1}^{\prime\prime}:=X_{1}^{\prime\prime\prime}\cup\{v\}\cup\{v_{i}:i\equiv 0% \pmod{3}\}$ , and $X_{2}^{\prime\prime}:=X_{2}^{\prime\prime\prime}\cup\{v_{i}:i\equiv 1\pmod{3}\}$ . Then $v\in X_{1}^{\prime\prime}$ , $X_{1}^{\prime\prime}$ and $X_{2}^{\prime\prime}$ each dominate $H^{\prime\prime}$ , and $X_{0}^{\prime\prime}$ dominates $V(H^{\prime\prime})\setminus\{v\}$ . We can now define the sets $X_{0}$ , $X_{1}$ , and $X_{2}$ exactly as we did in the previous paragraph. $\hfill\blacktriangleleft$

At last, the following lemma, illustrated in Figure 16, shows how we combine everything to find three sets whose total size is at most $2|B(H-B(H))|+|I(H-B(H))|$ .

Figure 16: Lemma 16: Finding three sets

X_{0}

,

X_{1}

, and

X_{2}

that dominate

I(H)

in a

2

-critical graph

H

.

Lemma 16.

Let $H$ be a $2$ -critical generalized near-triangulation. Then there exists $X_{0},X_{1},X_{2}\subseteq V(H)$ such that

(i)

$|X_{0}|+|X_{1}|+|X_{2}|\leq 2|B(H-B(H))|+|I(H-B(H))|$ ;
(ii)

for each $i\in\{0,1,2\}$ , $X_{i}$ dominates $I(H)$ in $H$ ; and
(iii)

for each $i\in\{0,1,2\}$ , each component of $H[X_{i}]$ contains at least one vertex in $B(H)$ .

Proof of Lemma 10.

Take $X$ to be the smallest of the three sets $X_{0}$ , $X_{1}$ , and $X_{2}$ guaranteed by Lemma 16. $\hfill\blacktriangleleft$

3.6 The Algorithm

All of this has been leading up to a variant $\textsc{SimpleGreedy}(G)$ that we call $\textsc{BetterGreedy}(G)$ . Suppose we have already chosen $\Delta_{0},\ldots,\Delta_{i-1}$ for some $i\geq 0$ and we now want to choose $\Delta_{i}$ . Let $X_{i}:=\bigcup_{j=0}^{i-1}\Delta_{j}$ , let $G_{i}$ be a dom-minimal graph that dom-respects $G-X_{i}$ , and let $v_{i}$ be a vertex in $B(G_{i})$ that maximizes $\deg^{+}_{G_{i}}(v_{i})$ . During iteration $i\geq 0$ , there are now more cases to consider:

[bg1]

If $\deg^{+}_{G_{i}}(v_{i})\geq 3$ then we set $\Delta_{i}:=\{v_{i}\}$ .
[bg2]

Otherwise, if $G_{i}-B(G_{i})$ contains a vertex of degree $1$ we set $\Delta_{i}:=\{v_{i}\}$ where $v_{i}$ is the vertex $v$ guaranteed by Lemma 8.
[bg3]

Otherwise, if $G_{i}-B(G_{i})$ contains a vertex of degree $0$ we set $\Delta_{i}:=\{v_{i}\}$ where $v_{i}$ is the vertex $v$ guaranteed by Lemma 9.
[bg4]

Otherwise, if there exists distinct $u,v\in B(G_{i})$ and $w\in B(G_{i}-B(G_{i}))$ such that $\deg^{+}_{G_{i}}(v)=2$ , $\deg^{+}_{G_{i}-v}(w)\geq 3$ , and $N^{+}_{G_{i}}(u)\subseteq N_{G_{i}}(w)$ then set $\Delta_{i}:=\{v,w\}$ .
[bg5]

Otherwise, $G_{i}$ is $2$ -critical and $i+1=:r$ . By Lemma 10, there exists $\Delta_{r-1}\subseteq V(G_{i})$ of size at most $2|B(G_{i}-B(G_{i}))|/3+|I(G_{i}-B(G_{i}))|/3$ that dominates $I(G_{i})$ .

Theorem 3.

When applied to an $n$ -vertex triangulation $G$ , $\textsc{BetterGreedy}(G)$ produces a connected dominating set $X_{r}$ of size at most $(10n-18)/21$ .

Proof.

By Lemmata 8, 9, and 7 during each of the first $r-1$ steps, one of the following occurs:

$x_{t}$ :: For some $t\geq 3$ , we can add a single vertex $v_{i}$ that increases the size of the dominated set $D_{i+1}:=N[X_{i+1}]$ by $t$ and increases the size of the boundary set $B_{i+1}:=N_{G}(I(G-D_{i+1}))$ by at most $t-1$ .
$a$ :: We can add a vertex $v_{i}$ that increases the size of the dominated set $D_{i+1}$ by $2$ and decreases the size of the boundary set $B_{i+1}$ by at least $1$ .
$b$ :: We can add a vertex $v_{i}$ that increases the size of the dominated set $D_{i+1}$ by $1$ and decreases the size of the boundary set $B_{i+1}$ by at least $3$ .
$c$ :: We can add a pair of vertices $\{v_{i},w_{i}\}$ that increase the size of the dominated set $D_{i+1}$ by at least $5$ and increases the size of the boundary set $B_{i+1}$ by at most $2$ .
$\bullet$ :: We can directly complete the connected dominating set $X_{r}=X_{i+1}$ by adding a set $\Delta_{r-1}=\Delta_{i}$ of at most $(2|B(G_{i}-B(G_{i}))|+|I(G_{i}-B(G_{i}))|)/3$ additional vertices where, as before $G_{i}:=G[B_{i}\cup(V(G)\setminus D_{i})]$ and $r=i+1$ .

Refer to Figure 17. Let $a$ , $b$ , $c$ , and $\langle x_{t}\rangle_{t\geq 3}$ denote the number of times each of these cases occurs in the first $r-1$ steps, and let $D:=D_{r-1}$ , $B:=B_{r-1}$ , and $X:=X_{r-1}$ . Then,

$\displaystyle\|D\|$	$\displaystyle\geq 3+\sum_{t\geq 3}tx_{t}+2a+b+5c$	(3)
$\displaystyle\|B\|$	$\displaystyle\leq 3+\sum_{t\geq 3}(t-1)x_{t}-a-3b+2c\enspace$	(4)
$\displaystyle\|X\|$	$\displaystyle\leq\sum_{t\geq 3}x_{t}+a+b+2c\enspace.$	(5)

Figure 17: The sets

X

,

D

,

B

,

R

, and

S

.

Let $R:=B(G_{r-1}-B(G_{r-1}))$ and $S:=I(G_{r-1}-B(G_{r-1}))$ . Since $\{D,R,S\}$ is a partition of $V(G)$ ,

|D|+|R|+|S|=n\enspace.

(6)

By Lemma 12, $|B_{r-1}|\geq|B(G_{i}-B(G_{i}))|$ , i.e., $|B|\geq|R|$ . Putting everything together we get the constraints:

	$\displaystyle 3+\sum_{t\geq 3}tx_{t}+2a+b+5c+\|R\|+\|S\|\leq n$	(by Equation 3 and Equation 6)		(7)
	$\displaystyle 3+\sum_{t\geq 3}(t-1)x_{t}-a-3b+2c\geq\|R\|$	(by Equation 4 and since $\|B\|\geq\|R\|$ )		(8)

with all values non-negative. The size of the final connected dominating set $X_{r}$ is then at most

|X_{r}|=|X|+|\Delta_{r-1}|\leq\sum_{t\geq 3}x_{t}+a+b+2c+2|R|/3+|S|/3\enspace.

(9)

Claim 1.

If $(a,b,c,|R|,|S|,x_{3},x_{4},\ldots)$ are non-negative and satisfy Equations 7 and 8, then setting $x_{3}\leftarrow x_{3}+\sum_{t\geq 4}(t-1)x_{t}/3$ and $x_{t}\leftarrow 0$ for all $t\geq 4$ also satisfy Equations 7 and 8 and do not decrease Equation 9.

Proof.

Suppose $x_{t}>0$ for some integer $t\geq 4$ , otherwise there is nothing to prove. Let $i:=\min\{t\geq 4:x_{t}>0\}$ and set $x_{3}\leftarrow x_{3}+(t-1)x_{t}/3$ and $x_{t}\leftarrow 0$ . This change causes the left-hand-side of Equation 7 to decrease by $x_{t}$ . This change does not affect the left-hand-side of Equation 8. This change increases the value of Equation 9 by $(t-1)x_{t}/3-x_{t}\geq 0$ . $\hfill\vartriangleleft$

By Claim 1, maximizing Equation 9 subject to the constraints given by Equations 7 and 8 is a linear program in six variables $(x_{3},a,b,c,|R|,|S|)$ which can be done easily. The maximum is achieved when $x_{3}=a=b=c=|S|=0$ , $c=(n-6)/7$ and $|R|=(2n+9)/7$ , at which point Equation 9 evaluates to $(10n-18)/21$ . $\hfill\blacktriangleleft$

Theorem 3 establishes the combinatorial result in Theorem 1 and the following theorem establishes the algorithmic result.

Theorem 4.

There exists a linear-time algorithm that implements $\textsc{BetterGreedy}(G)$ .

4 An Application in Graph Drawing

This section demonstrates applications of connected dominating sets and, in particular, our main result to graph drawing. In particular, we present an application of our main result to two graph drawing problems: one-bend free sets and simultaneous embeddings.

4.1 One-Bend Free Sets

For a planar graph $G$ , a set $Y\subseteq V(G)$ is called a free set if, for every $|Y|$ -point set $P\subseteq\mathbb{R}^{2}$ , there exists a non-crossing drawing in the plane with edges of $G$ drawn as line segments and such that the vertices of $Y$ are drawn on the points of $P$ . (For historical reasons, the set $Y$ is also called a collinear set.) It is known that every $n$ -vertex planar graph has a free set of size $\Omega(\sqrt{n})$ [5, 15, 16]. For bounded-degree planar graphs, this result can be improved to $|Y|=\Omega(n^{0.8})$ [17]. Determining the supremum value of $\alpha$ such that every $n$ -vertex planar graph has a collinear set of size $\Omega(n^{\alpha})$ remains a difficult open problem, but it is known that $\alpha\leq\log_{23}(22)<0.9859$ [31]. A history of free sets and their applications in graph drawing and related areas is surveyed by [18].

It is common in graph drawing to consider non-crossing drawings of a graph $G$ in which each edge of $G$ is represented by a polygonal chain consisting of at most $k+1$ line segments. Such a representation is called a $k$ -bend drawing of $G$ (so a straight-line drawing is a $0$ -bend drawing). A subset $Y$ of $V(G)$ is a $k$ -bend free set if, for every $|Y|$ -point set $P$ , $G$ has a $k$ -bend drawing in which the vertices of $Y$ are mapped to the points in $P$ . In [27], they show that, for any planar graph $G$ , $V(G)$ is a $2$ -bend free set, so every $n$ -vertex planar graph has a $2$ -bend free set of size $n$ . This leaves open the question of $1$ -bend free sets. In Lemma 17, we show that, for any spanning tree $T$ of $G$ , the leaves of $T$ are a one-bend free set of $G$ . Combined with Theorem 1, this gives:

Theorem 5.

For every $n\geq 3$ , every $n$ -vertex planar graph has a one-bend free set $L$ of size at least $11n/21=0.\overline{523809}n$ . Furthermore, there exists an $O(n)$ time algorithm for finding $L$ .

Note that if the point set $P$ is contained in the $x$ -axis then, in a $1$ -bend drawing, no edge with both endpoints in $Y$ crosses the $x$ -axis. Therefore, such a $1$ -bend drawing gives a $2$ -page book-embedding of the induced graph $G[Y]$ . This implies that $G[Y]$ is a spanning subgraph of some Hamiltonian triangulation $G[Y]^{+}$ . The Goldner–Harary graph is an $11$ -vertex triangulation that is not Hamiltonian. It follows that the graph $G$ obtained by taking $k$ vertex-disjoint copies of the Goldner-Harary graph has $n:=11k$ vertices and has no one-bend free set of size greater than $10k=10n/11=0.90\overline{90}n$ .

In the remainder of this subsection we prove Theorem 5. We start by introducing a topological equivalent of one-bend collinear sets as in [11].

A curve $C$ is a continuous mapping from $[0,1]$ to $\mathbb{R}^{2}$ . We usually call $C(0)$ and $C(1)$ the endpoints of $C$ . If $C(0)=C(1)$ then the curve is closed. Otherwise, it is open. A curve $C$ is called simple if $C$ is $C(x)\neq C(y)$ for all $0\leq x<y\leq 1$ with the exception of $x=0$ , $y=1$ . $C$ is a Jordan Curve if it is simple and closed.

Let $G$ be plane graph, a Jordan curve $C$ is a $k$ -proper good curve if it contains a point in the interior of some face of $G$ (good), and the intersection between $C$ and each edge $e$ of $G$ is empty, or at most $k$ points, or the entire edge $e$ ( $k$ -proper).

In [11], they characterize collinear sets in the straight line drawing of a planar graph using 1-proper good curves.

Theorem 6 ([11] ).

Let $G$ be a plane graph. A set $S\subseteq V(G)$ is a collinear set if and only if there exists a $1$ -proper good curve that contains $S$ .

The following lemma, illustrated in Figure 18, gives a similar condition for one-bend collinear sets.

$\Downarrow$

Figure 18: Subdividing

G

so that a

2

-proper good curve

C

becomes a

1

-proper good curve for the subdivided graph

G^{+}

.

Observation 4.

Let $G$ be a plane graph. A set $S\subseteq V(G)$ is a one-bend collinear set if $G$ has a $2$ -proper good curve $C$ that contains $S$ .

We next prove that the leaves of a spanning tree of a planar graph induce a one-bend collinear set. Precisely, we prove the following theorem.

Lemma 17.

Let $G$ be a planar graph and $T$ be a spanning tree of $G$ . Then, the leaves of $T$ form a one-bend collinear set for $G$ .

Proof.

Let $\Gamma$ be a straight-line drawing of $G$ . By Observation 4, it is enough to introduce a 2-proper good curve $\ell$ on $\Gamma$ containing all the leaves of $T$ . To navigate the curve $\ell$ on the drawing $\Gamma$ , we construct an envelope around $\Gamma$ as follows. For each vertex $v\in V(G)$ , we draw a small circle, $C_{v}$ , centered at $v$ . We make the radii of the circles small enough such that each vertex $v\in V(G)$ , $C_{v}$ intersects only the edges incident to $v$ and it is disjoint from all the other circles that correspond to the other vertices. Moreover, for each edge $uv\in E(G)$ , we draw two parallel segments on both sides of $u v$ with endpoints on the boundary of corresponding circles of $u$ and $v$ . These parallel segments are close enough to the corresponding edges such that no two of them intersect. (see Figure 19). Note that each edge $uv\in E(G)$ crosses the envelope exactly twice, once at $C_{u}$ and once at $C_{v}$ .

$\Downarrow$

Figure 19: Constructing a

2

-proper good curve for

G

that contains all the leaves of the tree

T

.

Assume $T$ is rooted at an arbitrary vertex of degree at least 2. We build the curve $\ell$ on the envelope of $\Gamma$ as follows. Starting from the root, we traverse the tree in depth first search order. For each edge $uv\in E(T)$ , we add the segment on the right side of the traversal direction of $u v$ into the curve $\ell$ .

For each leaf $u$ of $T$ , let $v_{u}$ be its neighbor in $T$ . To include all the leaves of $T$ on the curve $\ell$ , we join $u$ to the endpoint of segments around the edge $uv_{u}\in E(T)$ on $C_{u}$ . To keep the curve $\ell$ closed, for each non-leaf vertex $u\in V(T)$ , we append to $\ell$ the circular arcs from $C_{u}$ between the segments in $\ell$ in the order of the traversal. By the properties of the depth first traversal, $\ell$ is a closed curve. By construction, $\ell$ contains all the leaves of $T$ and all the other vertices of $T$ are inside $\ell$ . Moreover, for each edge $uv\in E(G)$ :

(P1)

If $uv\in E(T)$ and neither $u$ nor $v$ is a leaf, then $|uv\cap\ell|=0$ ,
(P2)

If $uv\in E(T)$ and either $u$ or $v$ is a leaf of $T$ , then $|uv\cap\ell|=1$ , and
(P3)

If $uv\notin E(T)$ , then $|uv\cap\ell|=2$ .

Properties P1-P3 guarantee that $\ell$ is a 2-proper curve. Since the tree $T$ is not empty, $\ell$ intersects the circle of some vertex in $T$ , so $\ell$ touches a face of $\Gamma$ . Therefore, $\ell$ is $2$ -proper good curve and by Observation 4, there exists a one-bend collinear set for $G$ formed by the leaves of $T$ . $\hfill\blacktriangleleft$

Proof of Theorem 5.

Let $G$ be an $n$ -vertex planar graph. Theorem 1 implies that $G$ has a spanning tree with at least $11n/21$ leaves that can be computed in $O(n)$ time. Using this tree in Lemma 17 establishes Theorem 5. $\hfill\blacktriangleleft$

4.2 Simultaneous Embedding with Fixed Edges and Without Mapping

A planar graph equipped with a non-crossing embedding is called a plane graph. We treat any subgraph $G^{\prime}$ of a plane graph $G$ as a plane graph that inherits its embedding from $G$ . A plane graph in which all vertices appear on a single face is called an outerplane graph. Motivated by a graph drawing problem (called, simultaneous embedding with fixed Edges and without mapping), the authors of [2] prove the following result:

Theorem 7 ([2]).

Every $n$ -vertex plane graph $G$ (and therefore every triangulation) contains an induced outerplane graph $G[L]$ with at least $n/2$ vertices.

Observe that if $G$ is a connected plane graph and $X$ is a connected dominating set of $G$ , then the vertices of $X$ are all contained in the interior of a single face $F$ of $G-X$ . Since $X$ is a dominating set, every vertex of $G-X$ is on the face $F$ . Thus, all vertices of $G-X$ are on a single face, so $G-X$ is an induced outerplane graph.

Combined with Theorem 1, this implies the following improvement of Theorem 7:

Corollary 2.

Every connected $n$ -vertex plane graph $G$ contains an induced outerplane graph $G^{\prime}$ with at least $11n/21=0.\overline{523809}n$ vertices, and there exists an $O(n)$ time algorithm to find the graph $G^{\prime}$ .

Corollary 2 immediately implies an improved result for the graph drawing problem considered by [2], improving the bound from $n/2$ to $11n/21$ :

Theorem 8.

For every $n$ -vertex planar graph $G_{1}$ and every $\lceil 11n/21\rceil$ -vertex planar graph $G_{2}$ , there exists point sets $P_{1}\supseteq P_{2}$ with $|P_{1}|=n$ , $|P_{2}|=\lceil 11n/21\rceil$ and crossing-free embeddings of $G_{1}$ and $G_{2}$ such that

(a)

the vertices of $G_{i}$ are mapped to the points in $P_{i}$ for each $i\in\{1,2\}$ ;
(b)

the edges of $G_{2}$ are drawn as line segments; and
(c)

each edge $e$ of $G_{1}$ whose endpoints are both mapped to points in $P_{2}$ is drawn as a line segment.

We end this section with the following observation. We argued above that if $X$ is a connected dominating set in a triangulation $G$ , then the induced graph $G[V(G)\setminus X]$ is an outerplane graph. Although it is not immediately obvious, finding the largest induced outerplane graph in a triangulation $G$ is equivalent to the problem of finding the smallest connected dominating set.

Theorem 9.

Let $G$ be a triangulation with $n\geq 4$ vertices, let $X$ be a minimum-sized connected dominating set of $G$ , and let $Y$ be a maximum-sized subset of $V(G)$ such that all vertices of $G[Y]$ lie on a common face of $G[Y]$ . Then $|X|+|Y|=n$ .

Proof.

Let $X$ be a minimum-size connected dominating set of $G$ and let $Y^{\prime}=V(G)\setminus X$ . Then $G[Y^{\prime}]$ is outerplane, since every vertex in $Y^{\prime}:=V(G)\setminus X$ is on the boundary of the face of $G[Y]$ that contains all vertices of $X$ in its interior. Since $Y$ has maximum size $|X|+|Y|\geq|X|+|Y^{\prime}|=n$ .

Now consider a set $Y$ of maximum size such that all vertices of $G[Y]$ lie on a common face $F_{Y}$ of $G[Y]$ and, among all such maximum-size sets, choose $Y$ to maximize the number of vertices of $G$ that are contained in the interior of $F_{Y}$ . Without loss of generality, suppose $F_{Y}$ is the outer face of $G[Y]$ , so $G[Y]$ is outerplane. Let $X^{\prime}:=V(G)\setminus Y$ . Since $n\geq 4$ , $Y$ does not contain all three vertices on the outer face of $G$ , so $X^{\prime}$ dominates the vertices on the outer face of $G$ . For any vertex $w\in Y$ not on the outer face of $G$ , some neighbour of $v\in N_{G}(w)$ is in $X^{\prime}$ since, otherwise $G[N_{G}(v)]\subseteq G[Y]$ contains a cycle with $w$ in its interior, contradicting the fact that $G[Y]$ is outerplane. Therefore $X^{\prime}$ is a dominating set of $G$ .

We now show that all vertices of $X^{\prime}$ are in the outer face of $G[Y]$ , which implies that $G[X^{\prime}]$ is connected. Suppose, by way of contradiction, that some inner face $F$ of $G[Y]$ contains at least one vertex of $X^{\prime}$ in its interior. Since $G$ is connected, there is at least one vertex $v\in V(F)$ such that $N_{G}(v)$ contains at least one vertex in the interior of $F$ . Let $Z:=\{w\in N_{G}(v):\text{$w$ is in the interior of $F$}\}$ . Let $Y^{\prime}:=Y\cup Z\setminus\{v\}$ . Then $|Y^{\prime}|\geq|Y|$ , $G[Y^{\prime}]$ is outerplane, and the outer face of $G[Y^{\prime}]$ contains more vertices of $G$ than $F_{Y}$ . This contradicts the choice of $Y$ .

Therefore $X^{\prime}$ is a connected dominating set of $G$ . Since $X$ is of minimum size, $|X|+|Y|\leq|X^{\prime}|+|Y|=n$ . Therefore $n\leq|X|+|Y|\leq n$ , so $|X|+|Y|=n$ , as required. $\hfill\blacktriangleleft$

5 Conclusions

In this paper, we broke the longstanding $n/2$ barrier for connected dominating sets in triangulations, showing that every triangulation admits a connected dominating set of size at most $10n/21$ (and that it can be computed in optimal, linear time). This result narrows the gap to the best-known lower bound and has applications to graph drawing.

We conclude with two natural open questions:

1.

What is the minimum value $c$ such that every $n$ -vertex triangulation (with $n\geq 3$ ) has a connected dominating set of size at most $cn+O(1)$ ? Our main result, Theorem 1, and the recent lower bound [19] imply that $7/18\leq c\leq 10/21$ .
2.

What is the maximum value $\alpha$ such that every $n$ -vertex planar graph contains a one-bend collinear set of size $\alpha n-O(1)$ ? Theorem 5 shows $\alpha\geq 11/21$ and disjoint copies of the Goldner-Harary graph show that $\alpha\leq 10/11$ .

References

[1] Michael O. Albertson, David M. Berman, Joan P. Hutchinson, and Carsten Thomassen. Graphs with homeomorphically irreducible spanning trees. J. Graph Theory, 14(2):247–258, 1990. doi:10.1002/JGT.3190140212.
[2] Patrizio Angelini, William S. Evans, Fabrizio Frati, and Joachim Gudmundsson. SEFE without mapping via large induced outerplane graphs in plane graphs. J. Graph Theory, 82(1):45–64, 2016. doi:10.1002/JGT.21884.
[3] Paul Bonsma and Florian Zickfeld. A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. SIAM Journal on Discrete Mathematics, 25(4):1652–1666, 2011. doi:10.1137/100801251.
[4] Paul S. Bonsma. Spanning trees with many leaves in graphs with minimum degree three. SIAM Journal on Discrete Mathematics, 22(3):920–937, 2008. doi:10.1137/060664318.
[5] Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, and David R. Wood. A polynomial bound for untangling geometric planar graphs. Discret. Comput. Geom., 42(4):570–585, 2009. doi:10.1007/S00454-008-9125-3.
[6] Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of spanning trees with many or few leaves. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 24:1–24:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ESA.2020.24.
[7] Peter Bradshaw, Tomás Masarík, Jana Novotná, and Ladislav Stacho. Robust connectivity of graphs on surfaces. SIAM J. Discret. Math., 36(2):1416–1435, 2022. doi:10.1137/21M1417077.
[8] Guantao Chen, Han Ren, and Songling Shan. Homeomorphically irreducible spanning trees in locally connected graphs. Comb. Probab. Comput., 21(1-2):107–111, 2012. doi:10.1017/S0963548311000526.
[9] Guantao Chen and Songling Shan. Homeomorphically irreducible spanning trees. Journal of Combinatorial Theory, Series B, 103(4):409–414, 2013. doi:10.1016/j.jctb.2013.04.001.
[10] Aleksander B. G. Christiansen, Eva Rotenberg, and Daniel Rutschmann. Triangulations admit dominating sets of size 2n/7. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1194–1240. SIAM, 2024. doi:10.1137/1.9781611977912.47.
[11] Giordano Da Lozzo, Vida Dujmović, Fabrizio Frati, Tamara Mchedlidze, and Vincenzo Roselli. Drawing planar graphs with many collinear vertices. J. Comput. Geom., 9(1):94–130, 2018. doi:10.20382/jocg.v9i1a4.
[12] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
[13] Guoli Ding, Thor Johnson, and Paul D. Seymour. Spanning trees with many leaves. J. Graph Theory, 37(4):189–197, 2001. doi:10.1002/JGT.1013.
[14] Ding-Zhu Du and Peng-Jun Wan. Connected Dominating Set: Theory and Applications, volume 77 of Springer Optimization and Its Applications. Springer, New York, NY, 2013. doi:10.1007/978-1-4614-5242-3.
[15] Vida Dujmović. The utility of untangling. J. Graph Algorithms Appl., 21(1):121–134, 2017. doi:10.7155/JGAA.00407.
[16] Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote. Every collinear set in a planar graph is free. Discret. Comput. Geom., 65(4):999–1027, 2021. doi:10.1007/S00454-019-00167-X.
[17] Vida Dujmović and Pat Morin. Dual circumference and collinear sets. Discret. Comput. Geom., 69(1):26–50, 2023. doi:10.1007/S00454-022-00418-4.
[18] Vida Dujmović and Pat Morin. Free sets in planar graphs: History and applications. CoRR, abs/2403.17090, 2024. doi:10.48550/arXiv.2403.17090.
[19] Kengo Enami, Naoki Matsumoto, and Takamasa Yashima. Contributions to conjectures on planar graphs: Induced subgraphs, treewidth, and dominating sets, 2025. arXiv:2506.10471.
[20] Ira M. Gessel. Good will hunting’s problem: Counting homeomorphically irreducible trees, 2023. arXiv:2305.03157.
[21] Jonathan L. Gross and Thomas W. Tucker. Topics in Topological Graph Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009.
[22] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Domination in Graphs Volume 2: Advanced Topics. Routledge, New York, 1998. doi:10.1201/9781315141428.
[23] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Topics in Domination in Graphs. Developments in Mathematics. Springer, 2020. doi:10.1007/978-3-030-51117-3.
[24] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Domination in Graphs: Core Concepts. Springer Monographs in Mathematics. Springer, 2023. doi:10.1007/978-3-031-09496-5.
[25] Arthur Hoffmann-Ostenhof, Kenta Noguchi, and Kenta Ozeki. On homeomorphically irreducible spanning trees in cubic graphs. J. Graph Theory, 89(2):93–100, 2018. doi:10.1002/JGT.22242.
[26] Taisei Ito and Shoichi Tsuchiya. Degree sum conditions for the existence of homeomorphically irreducible spanning trees. J. Graph Theory, 99(1):162–170, 2022. doi:10.1002/JGT.22732.
[27] Michael Kaufmann and Andreas Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115–129, 2002. doi:10.7155/JGAA.00046.
[28] Daniel J. Kleitman and Douglas B. West. Spanning trees with many leaves. SIAM Journal on Discrete Mathematics, 4(1), February 1991. doi:10.1137/0404010.
[29] Lesley R. Matheson and Robert Endre Tarjan. Dominating sets in planar graphs. Eur. J. Comb., 17(6):565–568, 1996. doi:10.1006/EUJC.1996.0048.
[30] Kenta Noguchi and Carol T. Zamfirescu. Spanning trees for many different numbers of leaves. CoRR, abs/2312.13674, 2023. doi:10.48550/arXiv.2312.13674.
[31] Alexander Ravsky and Oleg Verbitsky. On collinear sets in straight-line drawings. In Petr Kolman and Jan Kratochvíl, editors, Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers, volume 6986 of Lecture Notes in Computer Science, pages 295–306. Springer, 2011. doi:10.1007/978-3-642-25870-1_27.
[32] Ivan Stojmenovic. Dominating sets in wireless networks. In Ivan Stojmenovic, editor, Handbook of Wireless Networks and Mobile Computing, pages 499–528. Wiley, 2002.
[33] Simon Špacapan. The domination number of plane triangulations. J. Comb. Theory, Ser. B, 143:42–64, 2020. doi:10.1016/J.JCTB.2019.11.005.

[bib.bib1] [1] Michael O. Albertson, David M. Berman, Joan P. Hutchinson, and Carsten Thomassen. Graphs with homeomorphically irreducible spanning trees. J. Graph Theory, 14(2):247–258, 1990. doi:10.1002/JGT.3190140212.

[bib.bib2] [2] Patrizio Angelini, William S. Evans, Fabrizio Frati, and Joachim Gudmundsson. SEFE without mapping via large induced outerplane graphs in plane graphs. J. Graph Theory, 82(1):45–64, 2016. doi:10.1002/JGT.21884.

[bib.bib3] [3] Paul Bonsma and Florian Zickfeld. A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. SIAM Journal on Discrete Mathematics, 25(4):1652–1666, 2011. doi:10.1137/100801251.

[bib.bib4] [4] Paul S. Bonsma. Spanning trees with many leaves in graphs with minimum degree three. SIAM Journal on Discrete Mathematics, 22(3):920–937, 2008. doi:10.1137/060664318.

[bib.bib5] [5] Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, and David R. Wood. A polynomial bound for untangling geometric planar graphs. Discret. Comput. Geom., 42(4):570–585, 2009. doi:10.1007/S00454-008-9125-3.

[bib.bib6] [6] Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of spanning trees with many or few leaves. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 24:1–24:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ESA.2020.24.

[bib.bib7] [7] Peter Bradshaw, Tomás Masarík, Jana Novotná, and Ladislav Stacho. Robust connectivity of graphs on surfaces. SIAM J. Discret. Math., 36(2):1416–1435, 2022. doi:10.1137/21M1417077.

[bib.bib8] [8] Guantao Chen, Han Ren, and Songling Shan. Homeomorphically irreducible spanning trees in locally connected graphs. Comb. Probab. Comput., 21(1-2):107–111, 2012. doi:10.1017/S0963548311000526.

[bib.bib9] [9] Guantao Chen and Songling Shan. Homeomorphically irreducible spanning trees. Journal of Combinatorial Theory, Series B, 103(4):409–414, 2013. doi:10.1016/j.jctb.2013.04.001.

[bib.bib10] [10] Aleksander B. G. Christiansen, Eva Rotenberg, and Daniel Rutschmann. Triangulations admit dominating sets of size 2n/7. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 1194–1240. SIAM, 2024. doi:10.1137/1.9781611977912.47.

[bib.bib11] [11] Giordano Da Lozzo, Vida Dujmović, Fabrizio Frati, Tamara Mchedlidze, and Vincenzo Roselli. Drawing planar graphs with many collinear vertices. J. Comput. Geom., 9(1):94–130, 2018. doi:10.20382/jocg.v9i1a4.

[bib.bib12] [12] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.

[bib.bib13] [13] Guoli Ding, Thor Johnson, and Paul D. Seymour. Spanning trees with many leaves. J. Graph Theory, 37(4):189–197, 2001. doi:10.1002/JGT.1013.

[bib.bib14] [14] Ding-Zhu Du and Peng-Jun Wan. Connected Dominating Set: Theory and Applications, volume 77 of Springer Optimization and Its Applications. Springer, New York, NY, 2013. doi:10.1007/978-1-4614-5242-3.

[bib.bib15] [15] Vida Dujmović. The utility of untangling. J. Graph Algorithms Appl., 21(1):121–134, 2017. doi:10.7155/JGAA.00407.

[bib.bib16] [16] Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote. Every collinear set in a planar graph is free. Discret. Comput. Geom., 65(4):999–1027, 2021. doi:10.1007/S00454-019-00167-X.

[bib.bib17] [17] Vida Dujmović and Pat Morin. Dual circumference and collinear sets. Discret. Comput. Geom., 69(1):26–50, 2023. doi:10.1007/S00454-022-00418-4.

[bib.bib18] [18] Vida Dujmović and Pat Morin. Free sets in planar graphs: History and applications. CoRR, abs/2403.17090, 2024. doi:10.48550/arXiv.2403.17090.

[bib.bib19] [19] Kengo Enami, Naoki Matsumoto, and Takamasa Yashima. Contributions to conjectures on planar graphs: Induced subgraphs, treewidth, and dominating sets, 2025. arXiv:2506.10471.

[bib.bib20] [20] Ira M. Gessel. Good will hunting’s problem: Counting homeomorphically irreducible trees, 2023. arXiv:2305.03157.

[bib.bib21] [21] Jonathan L. Gross and Thomas W. Tucker. Topics in Topological Graph Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009.

[bib.bib22] [22] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Domination in Graphs Volume 2: Advanced Topics. Routledge, New York, 1998. doi:10.1201/9781315141428.

[bib.bib23] [23] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Topics in Domination in Graphs. Developments in Mathematics. Springer, 2020. doi:10.1007/978-3-030-51117-3.

[bib.bib24] [24] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning. Domination in Graphs: Core Concepts. Springer Monographs in Mathematics. Springer, 2023. doi:10.1007/978-3-031-09496-5.

[bib.bib25] [25] Arthur Hoffmann-Ostenhof, Kenta Noguchi, and Kenta Ozeki. On homeomorphically irreducible spanning trees in cubic graphs. J. Graph Theory, 89(2):93–100, 2018. doi:10.1002/JGT.22242.

[bib.bib26] [26] Taisei Ito and Shoichi Tsuchiya. Degree sum conditions for the existence of homeomorphically irreducible spanning trees. J. Graph Theory, 99(1):162–170, 2022. doi:10.1002/JGT.22732.

[bib.bib27] [27] Michael Kaufmann and Andreas Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115–129, 2002. doi:10.7155/JGAA.00046.

[bib.bib28] [28] Daniel J. Kleitman and Douglas B. West. Spanning trees with many leaves. SIAM Journal on Discrete Mathematics, 4(1), February 1991. doi:10.1137/0404010.

[bib.bib29] [29] Lesley R. Matheson and Robert Endre Tarjan. Dominating sets in planar graphs. Eur. J. Comb., 17(6):565–568, 1996. doi:10.1006/EUJC.1996.0048.

[bib.bib30] [30] Kenta Noguchi and Carol T. Zamfirescu. Spanning trees for many different numbers of leaves. CoRR, abs/2312.13674, 2023. doi:10.48550/arXiv.2312.13674.

[bib.bib31] [31] Alexander Ravsky and Oleg Verbitsky. On collinear sets in straight-line drawings. In Petr Kolman and Jan Kratochvíl, editors, Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers, volume 6986 of Lecture Notes in Computer Science, pages 295–306. Springer, 2011. doi:10.1007/978-3-642-25870-1_27.

[bib.bib32] [32] Ivan Stojmenovic. Dominating sets in wireless networks. In Ivan Stojmenovic, editor, Handbook of Wireless Networks and Mobile Computing, pages 499–528. Wiley, 2002.

[bib.bib33] [33] Simon Špacapan. The domination number of plane triangulations. J. Comb. Theory, Ser. B, 143:42–64, 2020. doi:10.1016/J.JCTB.2019.11.005.

Connected Dominating Sets in Triangulations

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

1.1 Outline

2 The General Strategy

Observation 1.

Lemma 1.

2.1 Critical Graphs

Lemma 2.

Lemma 3.

2.2 A Simple Algorithm

Theorem 2.

Proof.

3 A Better Algorithm: Proof of Theorem 1

3.1 Dom-Minimal Dom-Respecting Graphs

Observation 2.

Observation 3.

Lemma 4.

Proof.

3.2 Finding a 𝟐–𝟑 Combo

Lemma 5.

Lemma 6.

Lemma 7.

Corollary 1.

3.3 Eliminating Inner Leaves

Lemma 8.

3.4 Eliminating Inner Isolated Vertices

Lemma 9.

Proof.

3.5 𝟐-Critical Graphs

Lemma 10.

Lemma 11.

Lemma 12.

Lemma 13.

Lemma 14.

Lemma 15.

Proof.

Lemma 16.

Proof of Lemma 10.

3.6 The Algorithm

Theorem 3.

Proof.

Claim 1.

Proof.

Theorem 4.

4 An Application in Graph Drawing

4.1 One-Bend Free Sets

Theorem 5.

Theorem 6 ([11] ).

Observation 4.

Lemma 17.

Proof.

Proof of Theorem 5.

4.2 Simultaneous Embedding with Fixed Edges and Without Mapping

Theorem 7 ([2]).

Corollary 2.

Theorem 8.

Theorem 9.

Proof.

5 Conclusions

References

3.2 Finding a $2$ – $3$ Combo

3.5 $2$ -Critical Graphs