Separability of Witness Gabriel Drawings

Haase, Carolina; Kindermann, Philipp; Lenhart, William; Liotta, Giuseppe

doi:10.4230/LIPIcs.GD.2025.13

Separability of Witness Gabriel Drawings

Carolina Haase

Trier University, Germany Philipp Kindermann

Trier University, Germany William Lenhart

Williams College, Williamstown, MA, USA Giuseppe Liotta

University of Perugia, Italy

Abstract

A witness Gabriel drawing $\Gamma$ is a straight-line drawing of a graph in which any two vertices of $\Gamma$ are adjacent if and only if the disk having these vertices as antipodal points contains no element of a special set of points called witnesses. A witness Gabriel drawing is linearly separable if the vertices and the witnesses lie in opposite half-planes. We prove that every outerplanar graph has a linearly separable witness Gabriel drawing by introducing and studying a new type of drawing that we call a border parabola drawing. We then use border parabola drawings to characterize those triangle-free graphs that admit a linearly separable witness Gabriel drawing. We also consider witness Gabriel drawings where no witness lies in the interior of the convex hull of the vertex set, which we call convexly separable drawings. We construct witness Gabriel drawable graphs for which any witness Gabriel drawing must be convexly separable and that do not admit any linearly separable witness Gabriel drawing.

Keywords and phrases:

Proximity Drawings, Witness Gabriel Graphs, Geometric Graph Theory

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms ; Mathematics of computing

\rightarrow

Graph theory

Funding:

Research of Giuseppe Liotta supported in part by MUR PON Proj. ARS01 00540 and by MUR PRIN Project no. 2022TS4Y3N.

DOI:

10.4230/LIPIcs.GD.2025.13

Event:

33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Editors:

Vida Dujmović and Fabrizio Montecchiani

Series and Publisher:

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

1 Introduction

A proximity graph of a set of distinct points $S$ in the Euclidean plane is a geometric graph $G$ whose vertex set is $S$ . Any two vertices $u$ and $v$ of $G$ are adjacent if and only if no other vertex $w$ of $G$ is in the “neighborhood” of $u$ and $v$ . Depending on the definition of neighborhood, we have different types of proximity graphs. For example, in a Gabriel graph $u v$ is an edge if and only if the Gabriel disk, i.e., the disk having $u$ and $v$ as antipodal points, does not contain any other vertex $w$ . In a rectangle of influence drawing $u$ and $v$ are adjacent if and only if the rectangle of influence of $u$ and $v$ , i.e., the axis-parallel rectangle having $u$ and $v$ at opposite corners, does not contain any other vertex $w$ .

For a given definition of proximity, different graph topologies correspond to distinct distributions of their vertex sets, making these graphs effective descriptors of the morphological properties of point configurations (see, e.g., [18, 19]). As a consequence, proximity graphs find applications in a variety of contexts, including machine learning, wireless networks, computer vision, and business analytics (see, e.g., [5, 16, 19, 21]). In information visualization, proximity graphs are used to measure the faithfulness of network layouts (see, e.g., [6, 7, 11, 17, 10]).

From the graph drawing perspective, a proximity graph is a straight-line drawing where adjacent vertices are close to one another while pairs of non-adjacent vertices are far from each other according to a given definition of closeness. Partly motivated by the applications above, the study of which graph topologies can be realized for some definition of proximity is a well studied question that can be stated as the following graph drawing problem: Given a graph $G$ and a definition of proximity, does $G$ admit a straight-line drawing $\Gamma$ such that the proximity graph of the vertex set of $\Gamma$ is isomorphic to $G$ ? In the affirmative case, $\Gamma$ is a proximity drawing of $G$ and $G$ is said to be proximity drawable. See [15] for a survey on proximity drawings and the proximity drawability problem.

This paper studies witness proximity drawable graphs, i.e., graphs that can be realized as the witness proximity graph of some point sets. In a witness proximity graph we are given two sets of points: the vertices, and the witnesses that act as obstacles to the existence of the edges. Any two vertices $u$ and $v$ are adjacent if and only if there is no witness in the neighborhood of $u$ and $v$ . Hence, a witness Gabriel drawing of a given graph $G$ is computed by defining a set of points that act as vertices and a set of witnesses that act as obstacles; $u v$ is an edge in the drawing if and only if the Gabriel disk of $u$ and $v$ does not contain any witnesses. Note that the Gabriel disk of an edge $u v$ may contain other vertices and that a witness Gabriel drawing coincides with a Gabriel drawing if the witness set and the vertex set coincide. Figure 1(a) shows a witness Gabriel drawing $\Gamma$ of a tree where the Gabriel disk of edge $u v$ contains another vertex of $\Gamma$ .

(a)

(b)

(c)

Figure 1: (a) A witness Gabriel drawing, (b) a convexly separable witness Gabriel drawing, and (c) a linearly separable witness Gabriel drawing of a tree. The vertices are drawn as blue filled disks and the witnesses are drawn as red empty squares.

Motivated by the design of classifiers in pattern recognition applications, Ichino and Sklansky [12] use witness rectangle of influence graphs¹¹1These graphs are called interclass rectangular influence graphs in [12]. The term witness proximity graph and drawing was first used by Aronov, Hurtado and Dulieu in [1]. to study the correlations among different features, represented by points in the plane. Witness Gabriel graphs are introduced in a seminal paper by Aronov, Dulieu, and Hurtado [2] who also study the witness Gabriel drawability problem for different graph families, including trees and complete bipartite graphs. The same authors extend the results of Ichino and Sklansky about witness rectangle of influence graphs in [3] and study witness Delaunay graphs in [1]. It is worth remarking that both the early work of Ichino and Sklanksy [12] and the subsequent papers of Aronov, Dulieu, and Hurtado [1, 2, 3] stress the importance of the geometric separability between the vertex set and the witness set in a witness proximity graph, since this property provides useful information about the interclass structure of the two point sets.

This has motivated recent studies about witness Gabriel drawings where the witnesses are either linearly or convexly separable from the vertex set (see, e.g., [13, 14, 9]); the witness set is convexly separable from the vertex set when no witness is in the convex hull of the vertices. At first sight, one might think that the geometric separability of the witness set from the vertex set cannot give rise to sparse topologies. For example, the algorithm of Aronov, Dulieu, and Hurtado [2] to construct witness Gabriel drawings of trees places witnesses well in the interior of the convex hull of the vertex set. However, many sparse topologies are in fact realizable even with linear or convex separability constraints; furthermore, we will show that the geometric separability is actually required for some graph instances that include sparse graphs. Figure 1(b) is a convexly separable witness Gabriel drawing of the tree of Figure 1(a), while Figure 1(c) is a linearly separable one.

An outline of our results is as follows.

$\blacksquare$

We show that every outerplanar graph admits a linearly separable witness Gabriel drawing. This extends the result of Aronov, Dulieu, and Hurtado about the witness Gabriel drawability of trees by both enlarging the family of representable graphs and by proving the linear separability of the drawings. The linear separability property for witness Gabriel drawings of outerplanar graphs was previously known only for caterpillars [9].
$\blacksquare$

We prove that any triangle-free graph has a linearly separable witness Gabriel drawing if and only if it does not have $K_{2,3}$ as a minor; that is, if and only if the triangle-free graph is outerplanar [20]. This extends a result of [13, 14] where it is shown that the complete bipartite graphs admitting linearly separable witness Gabriel drawings are exactly those not containing $K_{2,3}$ as an (induced) subgraph.
$\blacksquare$

We investigate the relationship between convexly separable and linearly separable witness Gabriel drawable graphs. We construct infinitely many witness Gabriel drawable graphs which admit convexly separable drawings but do not have a linearly separable witness Gabriel drawing. In fact, we show that for any of these graphs, any witness Gabriel drawing must be convexly separable. We believe that identifying graphs whose witness Gabriel drawings require convex separability offers a novel perspective on the long-standing open problem of characterizing witness Gabriel drawable graphs [2].

Our construction of witness Gabriel drawings of outerplanar graphs depends on a new type of drawing which we call a border parabola drawing and that may be of interest in its own right. It is a type of drawing in which every vertex is associated with a convex region that contains it and such that there is an edge between two vertices if and only if one end-vertex of an edge is in the region of the other. Any border parabola drawing of a graph can be converted to a linearly separable witness Gabriel drawing with the addition of appropriately chosen witness locations.

2 Preliminaries

We assume familiarity with graph drawing terms and concepts (refer, for example, to [4]). We recall that the Gabriel disk of two distinct points $p$ , $q$ is the disk whose diameter is segment $p q$ . We denote the Gabriel disk of $p$ and $q$ as $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure0.pdf}}}}}[% p,q]$ . In the rest of the paper $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure1.pdf}}}}}[% p,q]$ is a closed set, which is the standard definition of Gabriel disks [8]. We also denote by $\triangle[u,v,w]$ the triangle whose corners are points $u$ , $v$ , and $w$ , and by $\overline{pq}$ the line through points $p$ and $q$ . The following lemma can be proved by elementary geometry.

Lemma 1.

Let $p$ , $q_{1}$ and $q_{2}$ be three non-collinear points and let $L$ be the line through $q_{1}$ and $q_{2}$ . Then the Gabriel disks $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure2.pdf}}}}}[% p,q_{1}]$ and $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure3.pdf}}}}}[% p,q_{2}]$ intersect at a point on $L$ and their union contains all points in $\triangle[p,q_{1},q_{2}]$ .

The lemma has some immediate consequences.

Corollary 2 ([2] Lemma 6).

Let $\Gamma$ be a witness Gabriel drawing, let $u v$ and $v w$ be two adjacent edges of $\Gamma$ . Then: (i) No witness is contained in $\triangle[u,v,w]$ , and (ii) any vertex in the interior of $\triangle[u,v,w]$ is adjacent to $v$ in $\Gamma$ .

Corollary 3 ([2] Proposition 1).

Let $\Gamma$ be a witness Gabriel drawing, and let $u v$ , $v w$ , and $u w$ be edges of $\Gamma$ forming a three-cycle. Any vertex $r\in\triangle[u,v,w]$ is adjacent to all of $\{u,v,w\}$ .

3 Witness Gabriel Drawings of Outerplanar Graphs

We prove here that every outerplanar graph admits a linearly separable witness Gabriel drawing. The drawings we produce have the additional property that for any edge, its Gabriel disk does not intersect the (open) half-plane containing the witnesses. To do this, we introduce and study a new type of graph drawing, which we call a border parabola drawing.

3.1 Border Parabola Drawings

Definition 4.

Given a point $p\in\mathbb{R}^{2}$ with $y(p)>0$ , the border parabola of $p$ is the set of points $q\in\mathbb{R}^{2}$ such that $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure4.pdf}}}}}[% p,q]$ is tangent to the x-axis. The border parabola of $p$ can be expressed by the function $f_{p}(x)=\frac{(x-x(p))^{2}}{4y(p)}$ .

Note that we use $x$ above both as a variable and as a projection function and that the border parabola of $p$ has $p$ as its focus and $(x(p),0)$ as its vertex. The following property is an immediate consequence of Section 3.1.

Property 1.

For any points $p$ and $q$ in the upper half-plane:

$\blacksquare$

if $y(p)>f_{q}(x(p))$ , then the Gabriel disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure5.pdf}}}}}[% p,q]$ lies above the $x$ -axis;
$\blacksquare$

if $y(p)=f_{q}(x(p))$ , then the $x$ -axis is tangent to $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure6.pdf}}}}}[% p,q]$ ;
$\blacksquare$

if $y(p)<f_{q}(x(p))$ , then the Gabriel disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure7.pdf}}}}}[% p,q]$ crosses the $x$ -axis.

For any point $q$ in the upper half-plane, let $B_{q}=\{p:y(p)\geq f_{q}(x(p))\}$ ; if $p\in B_{q}$ , we say that $p$ lies within the border parabola of $q$ . Property 1 immediately implies that $p$ lies within the border parabola of $q$ if and only if $q$ lies within the border parabola of $p$ , and in particular $p$ is a point of the border parabola of $q$ if and only if $q$ is a point of the border parabola of $p$ .

Definition 5.

Given a set $P$ of points in the upper half-plane, the graph $G=(P,E)$ , where $E=\{(p,q):q\in B_{p}\}$ is called the border parabola (or PB) graph of $P$ . The associated straight-line drawing, denoted by $\Gamma(P)$ , is called the border parabola drawing of $P$ .

Figure 2: A border parabola drawing of an outerplanar graph.

We say that $G$ admits a border parabola drawing if $G$ is the border parabola graph for some set $P$ ; if $G$ admits a border parabola drawing, we call $G$ a border parabola graph or say that $G$ is border parabola drawable. Figure 2 shows a border parabola drawing. The following properties will be useful:

Property 2.

Let $\Gamma(P)$ be a border parabola drawing and $\{p_{1},p_{2},p_{3}\}\subset P$ be such that $x(p_{1})<x(p_{2})<x(p_{3})$ . If $\{p_{1},p_{3}\}$ forms an edge and $p_{2}$ lies above $\overline{p_{1}p_{3}}$ , then $\{p_{1},p_{2}\}$ and $\{p_{2},p_{3}\}$ also form edges.

Proof.

Since the segment $\overline{p_{1}p_{3}}$ is contained in both $B_{p_{1}}$ and $B_{p_{3}}$ , the portion of the vertical strip determined by $\{p_{1},p_{3}\}$ that lies above $\overline{p_{1}p_{3}}$ is completely contained in $B_{p_{1}}\cap B_{p_{3}}$ and so $p_{2}$ must lie within both parabolas. Hence $\{p_{1},p_{2}\}$ and $\{p_{2},p_{3}\}$ also form edges. $\hfill\blacktriangleleft$

Property 3.

Let $\Gamma(P)$ be a border parabola drawing and let $\{p_{0},p_{1},p_{2}\}$ form a triangle in $\Gamma(P)$ . Then any point $p\in P\setminus\{p_{0},p_{1},p_{2}\}$ contained in the triangle $\triangle(p_{0},p_{1},p_{2})$ is adjacent to each of $\{p_{0},p_{1},p_{2}\}$ .

Proof.

It suffices to note that $\{p_{0},p_{1},p_{2}\}$ all lie in $B_{p_{0}}\cap B_{p_{1}}\cap B_{p_{2}}$ , which is a convex set and so contains every point in $\triangle(p_{0},p_{1},p_{2})$ . $\hfill\blacktriangleleft$

3.2 Border Parabola Drawings of Outerplanar Graphs

A witness Gabriel drawing $\Gamma(P,W)$ with vertex set $P$ and witness set $W$ of a graph $G$ is strongly linearly separable if there is a line separating $P$ from $W$ such that no Gabriel disk of an edge crosses the separating line. We shall say that $\Gamma$ is a SLSWG drawing of graph $G$ . We assume without loss of generality that the separating line is the $x$ -axis.

Property 1 implies that in a SLSWG drawing $\Gamma(P,W)$ , for any $p\in P$ , the border parabola of $p$ contains $p$ and its neighbors, but no other point of $P$ . That is, the drawing can be computed from $P$ alone, without reference to $W$ . Hence, we have the following.

Theorem 6.

A graph $G$ admits a SLSWG drawing $\Gamma(P,W)$ if and only if $G$ is the border parabola graph of $P$ .

The question of which graphs admit a SLSWG drawing is therefore the question: Which graphs $G$ are border parabola graphs? We are going to show that outerplanar graphs are border parabola graphs. We start with some definitions.

Let $p$ and $q$ be points in the plane such that $x(p)<x(q)$ . The (open) vertical strip for $p$ and $q$ is the set $S(p,q)=\{r:x(p)<x(r)<x(q)\}$ . The (open) lower half-strip for $p$ and $q$ $S^{-}(p,q)$ is the portion of $S(p,q)$ lying strictly below the line determined by $p$ and $q$ . Note that neither $p$ nor $q$ is contained in $S^{-}(p,q)$ or $S(p,q)$ because of the strict inequality used in the definitions.

Let $\Gamma(P)$ be a border parabola drawing and let $r\in\mathbb{R}^{2}$ be any point in the upper half-plane. We define the neighborhood of $r$ in $P$ to be the set $N_{P}(r)=B_{r}\cap P$ ; that is $N_{P}(r)$ is the set of points of $P$ that would be adjacent to $r$ in $\Gamma(P\cup\{r\})$ . Finally, for $\{p,q\}\subseteq P$ , we say that a subset $R$ of the upper half-plane is an extension zone for $\{p,q\}$ if

$\blacksquare$

for all $r\in R$ , $N_{P}(r)\subseteq\{p,q\}$ ,
$\blacksquare$

$R$ contains points $r_{1},\ldots,r_{4}$ such that $N_{P}(r_{1})=\emptyset$ , $N_{P}(r_{2})=\{p\}$ , $N_{P}(r_{3})=\{q\}$ , and $N_{P}(r_{4})=\{p,q\}$ .

The purpose of an extension zone is to identify, given points $\{p,q\}$ , a set of locations such that a point $r$ from the zone could be added to $P$ so that $\Gamma(P\cup\{r\})$ would contain the edges of $\Gamma(P)$ along with both, either, or neither of $\{\{p,r\},\{q,r\}\}$ but would contain no other additional edges.

Finally, let $\Gamma(P)$ be a border parabola drawing and let $\{p,q\}\subseteq P$ . The meet of $p$ and $q$ , denoted $m_{p,q}$ , is the point of $B_{p}\cap B_{q}$ having minimum $y$ -coordinate. The meet of $p$ and $q$ can be equivalently defined to be the point of intersection of $f_{p}$ and $f_{q}$ that lies in the vertical strip determined by $p$ and $q$ . Note that the portion of $B_{m_{p,q}}$ below the line determined by $p$ and $q$ is always a subset of $S^{-}(p,q)$ since $p$ and $q$ both lie on $f_{m_{p,q}}$ ; thus $m_{p,q}\in S^{-}(p,q)$ .

Lemma 7.

Let $\Gamma(P)$ be a border parabola drawing and let $\{p,q\}\subseteq P$ be such that $x(p)<x(q)$ , $S^{-}(p,q)\cap P=\emptyset$ and $N_{P}(m_{p,q})=\{p,q\}$ . Then there exists a disk $D_{s}$ centered at $s=m_{p,q}$ such that $D_{s}$ is an extension zone for $\{p,q\}$ , $D_{s}\subset S^{-}(p,q)$ , and every $r\in D_{s}$ satisfies

1.

$S^{-}(p,r)\cap P=\emptyset$ and $S^{-}(r,q)\cap P=\emptyset$ , and
2.

$N_{P\cup\{r\}}(m_{p,r})=\{p,r\}$ and $N_{P\cup\{r\}}(m_{r,q})=\{r,q\}$ ,

In other words, if the pair $\{p,q\}$ satisfies the hypotheses of Section 3.2 for $P$ , then any point $r$ that is close enough to $m_{p,q}$ has the property that both $\{p,r\}$ and $\{r,q\}$ satisfy the hypotheses of Section 3.2 for $P\cup\{r\}$ ; see Figure 3 for an illustration of the Lemma.

Proof.

Since $x(p)<x(q)$ and $B_{s}$ is a closed region, there exists an $\varepsilon>0$ such that the disk $D_{\varepsilon}(s)$ with radius $\varepsilon$ and center $s$ has the property that for any $s^{\prime}\in D_{\varepsilon}(s)$ , $N_{P}(s^{\prime})\subseteq N_{P}(s)=\{p,q\}$ . Consider any $\varepsilon^{\prime}$ such that $0<\varepsilon^{\prime}\leq\varepsilon$ . Since the border parabolas $f_{p}$ and $f_{q}$ intersect at $s$ , $f_{p}$ is strictly increasing at $s$ , and $f_{q}$ is strictly decreasing at $s$ , the points $p_{1}=(x(s),y(s)+\varepsilon^{\prime})$ , $p_{2}=(x(s)+\varepsilon^{\prime},y(s))$ , $p_{3}=(x(s),y(s)-\varepsilon^{\prime})$ , and $p_{4}=(x(s)-\varepsilon^{\prime},y(s))$ are all in $D_{\varepsilon}(s)$ and will satisfy $N_{P}(p_{1})=\{p,q\}$ , $N_{P}(p_{2})=\{q\}$ , $N_{P}(p_{3})=\emptyset$ , and $N_{P}(p_{4})=\{p\}$ respectively, so $D_{\varepsilon}(s)$ is an extension zone for $\{p,q\}$ . Also, if $S^{-}(p,q)\cap P=\emptyset$ , then for any $r\in S^{-}(p,q)$ , $S^{-}(p,r)\cap P=\emptyset$ and $S^{-}(r,q)\cap P=\emptyset$ , so the first condition is satisfied.

We now show that every $r\in D_{\varepsilon}(s)$ , satisfies $N_{P\cup\{r\}}(m_{p,r})=\{p,r\}$ ; the proof that $N_{P\cup\{r\}}(m_{r,q})=\{r,q\}$ is analogous. First note that since $S^{-}(p,q)\cap P=\emptyset$ , any point $t\in P\cap N_{P\cup\{r\}}(m_{p,r})$ other than $p$ lies in the portion of $N_{P\cup\{r\}}(m_{p,r})$ above the line $L$ determined by $p$ and $q$ . But that portion of $N_{P\cup\{r\}}(m_{p,r})$ is completely contained in $N_{P}(s)$ , since $f_{s}$ intersects $f_{m_{p,r}}$ at $p$ and at a point whose $x$ -coordinate is between those of $p$ and $r$ , and between $p$ and $r$ , $f_{m_{p,r}}$ lies below $f_{s}$ . This, and an analogous argument that $N_{P\cup\{r\}}(m_{r,q})=\{r,q\}$ , establish the second condition. Letting $D_{s}=D_{\varepsilon}(s)$ completes the proof. $\hfill\blacktriangleleft$

Figure 3: Illustration for Lemma 7.

Theorem 8.

Every outerplanar graph $G=(V,E)$ admits a border parabola drawing and hence it has a linearly separable witness Gabriel drawing.

Proof.

We incrementally construct a set $P$ and a function $g:P\rightarrow V$ such that at all times the border parabola graph $\Gamma(P)$ of $P$ is isomorphic to the subgraph of $G$ induced by $g(P)\subseteq V$ . We assume $G$ is connected; otherwise the construction is applied to each component of $G$ separately, translating successive components far enough to the right of previously drawn components so that if $\{u,v\}$ lie in different components, the Gabriel disk of $u$ and $v$ intersects the negative half-plane.

Assume that we have a topological embedding of $G$ . If $G$ is not a maximal outerplanar graph, add new edges $E^{\prime}$ to $G$ until $G^{\prime}=(V,E\cup E^{\prime})$ is maximal outerplanar. Note that this can be done so that the original embedding of $G$ is preserved. We use the geometric dual of $G^{\prime}$ to impose an order on the vertices of $G^{\prime}$ . Let $\{v_{1},v_{2}\}$ be an edge on the outer face of $G^{\prime}$ and let $v_{3}$ be their common neighbor. Now consider the tree whose vertices are the triangular faces of $G^{\prime}$ and whose edges connect faces of $G^{\prime}$ that share an edge. Root this tree at $\{v_{1},v_{2},v_{3}\}$ . We now order the remaining vertices so that the following invariant holds: For each $i>3$ , $v_{i}$ forms a triangle with some pair $\{v_{j},v_{k}\}$ such that $\{j,k\}$ are both less than $i$ (note that this also holds for $i=3$ by construction). Any such ordering will serve our purposes. We call $\{v_{j},v_{k}\}$ the parents of $v_{i}$ .

To begin the construction, if $\{v_{1},v_{2}\}\in E$ , let $\{p_{1},p_{2}\}$ be any two points such that $p_{2}\in B_{p_{1}}$ ; if $\{v_{1},v_{2}\}\in E^{\prime}$ , let $\{p_{1},p_{2}\}$ be any two points such that $p_{2}\not\in B_{p_{1}}$ and $m_{p_{1},p_{2}}\in S^{-}(p_{1},p_{2})$ . In either case, $\{p_{1},p_{2}\}$ can be chosen such that $x(p_{1})\not=x(p_{2})$ , and $y(p_{1})\not=y(p_{2})$ . Let $P=\{p_{1},p_{2}\}$ , $g(p_{1})=v_{1}$ , and $g(p_{2})=v_{2}$ . Note that $\Gamma(P)$ is isomorphic to the subgraph of $G$ (not $G^{\prime}$ !) induced by $\{v_{1},v_{2}\}$ .

At any point in the construction of $P$ , there will be pairs $\{p_{j},p_{k}\}\subset P$ such that $\{v_{j},v_{k}\}$ is an edge of $G^{\prime}$ and there exists a (unique) $m$ such that $\{v_{j},v_{k},v_{m}\}$ is a triangle of $G^{\prime}$ but $p_{m}$ has not yet been constructed. We call such a pair $\{p_{j},p_{k}\}$ pending.

One other structure that we will take advantage of will be the polygonal chain $C(P)$ consisting of the points in $P$ ordered by increasing $x$ -coordinate, with consecutive pairs forming line segments (note, some of these segments are edges of $\Gamma(P)$ but others may not be); $C(P)$ is a monotone chain with respect to the $x$ -axis. At all times, the next vertex $v_{i}$ of $G^{\prime}$ to be associated with a new point $p_{i}$ in $P$ will have the property that its parents are consecutive points in $C(P)$ . After $p_{i}$ is added to $P$ , the segment between the parents of $p_{i}$ in $C(P)$ is replaced by segments from $p_{i}$ to each of its parents. Since it will always be the case that the $x$ -coordinate of $p_{i}$ is between the $x$ -coordinates of its parents, $C(P)$ will remain monotone at all times.

We now describe how to add points to $P$ so that, for all $i$ with $1\leq i\leq n$ , after point $p_{i}$ has been added to $P$ , the following invariants hold:

1.

$\Gamma(P)$ is isomorphic to the subgraph of $G$ induced by $\{v_{1},\ldots,v_{i}\}$
2.

For every $j$ with $3\leq j\leq i$ , $p_{j}$ is contained in the lower half-strip of its parents
3.

The lower half-strips of any two pending pairs in $P$ are disjoint, and
4.
For every pending pair $\{p_{j},p_{k}\}$
1. (a)
  
  $\{p_{j},p_{k}\}$ appear as consecutive elements in $C(P)$
2. (b)
  
  $S^{-}(p_{j},p_{k})\cap P=\emptyset$ ,
3. (c)
  
  $m_{p_{j},p_{k}}\in S^{-}(p_{j},p_{k})$
4. (d)
  
  $N_{P}(m_{p_{j},p_{k}})=\{p_{j},p_{k}\}$

Note that the invariants hold (mostly vacuously) for $i=1$ and $i=2$ . So assume now that, for some value $i\geq 3$ , the invariants hold for $i-1$ . Let $\{v_{j},v_{k}\}$ be the parents of $v_{i}$ ; then $j,k:1\leq\{j,k\}\leq i-1$ and so $\{p_{j},p_{k}\}$ have already been added to $P$ , and so by invariant $4$ , $\{p_{j},p_{k}\}$ satisfy the hypotheses of Section 3.2. That is, letting $s=m_{p_{j},p_{k}}$ , there exists a disk $D_{s}$ with center $s$ such that $D_{s}$ is an extension zone for $\{p_{j},p_{k}\}$ , $D_{s}\subset S^{-}(p_{j},p_{k})$ , and such that every $r\in D_{s}$ satisfies

1.

$S^{-}(p_{j},r)\cap P=\emptyset$ and $S^{-}(r,p_{k})\cap P=\emptyset$ .
2.

$m_{p_{j},r}\in S^{-}(p_{j},r)$ and $m_{r,p_{k}}\in S^{-}(r,p_{k})$ , and
3.

$N_{P\cup\{r\}}(m_{p_{j},r})=\{p_{j},r\}$ and $N_{P\cup\{r\}}(m_{r,p_{k}})=\{r,p_{k}\}$ ,

We now choose a location for $p_{i}\in D_{s}$ as follows

$\blacksquare$

If $\{v_{j},v_{i}\}\in E$ and $\{v_{k},v_{i}\}\in E$ , choose $p_{i}$ so that $N_{P}(p_{i})=\{p_{j},p_{k}\}$ ,
$\blacksquare$

If $\{v_{j},v_{i}\}\in E$ and $\{v_{k},v_{i}\}\in E^{\prime}$ , choose $p_{i}$ so that $N_{P}(p_{i})=\{p_{j}\}$ ,
$\blacksquare$

If $\{v_{j},v_{i}\}\in E^{\prime}$ and $\{v_{k},v_{i}\}\in E$ , choose $p_{i}$ so that $N_{P}(p_{i})=\{p_{k}\}$ ,
$\blacksquare$

If $\{v_{j},v_{i}\}\in E^{\prime}$ and $\{v_{k},v_{i}\}\in E^{\prime}$ , choose $p_{i}$ so that $N_{P}(p_{i})=\emptyset$ .

Add $p_{i}$ to $P$ and let $g(p_{i})=v_{i}$ , and observe that by virtue of the selection rule for $p_{i}$ , $\Gamma(P)$ is still isomorphic to the subgraph of $G$ induced by $\{v_{1},\ldots,v_{i}\}$ . Also, $p_{i}$ is contained in the lower half-strip of its parents. In addition, since $S^{-}(p_{j},p_{i})$ and $S^{-}(p_{i},p_{k})$ are disjoint and contained in $S^{-}(p_{j},p_{k})$ , and $\{p_{j},p_{k}\}$ is no longer pending, the lower half-strips of all pending pairs are still disjoint, since $p_{i}$ can’t form a pending pair with any point of $P$ other than its parents $p_{j}$ and $p_{k}$ (the only neighbors in $G^{\prime}$ of $v_{i}$ in $\{v_{1},\ldots,v_{i-1}\}$ are $v_{j}$ and $v_{k}$ ). We thus just need to verify that conditions 4a-4d are still satisfied.

4a

Before $p_{i}$ was added, Condition 4a held. After $p_{i}$ is added, $\{p_{j},p_{k}\}$ is no longer a pending pair so $\{p_{j},p_{k}\}$ no longer need to be consecutive in $C(P)$ . The only possible new pending pairs are $\{p_{j},p_{i}\}$ and $\{p_{i},p_{k}\}$ ; both of these pairs occur as consecutive points in $C(P)$ . and so Condition 4a is satisfied.
4b

Similarly, Condition 4b is clearly satisfied since $p_{i}$ was added inside $S^{-}(p_{j},p_{k})$ and so after it has been added to $P$ , $p_{i}$ is not contained in the lower vertical strip of any pending pair since all such pairs have disjoint strips.
4c

Condition 4c is still satisfied for any pending pair not including $p_{i}$ , so it only needs to be checked for $S^{-}(p_{j},p_{i})$ and $S^{-}(p_{i},p_{k})$ (which may or may not be pending pairs). But the choice of location of $p_{i}$ along with Section 3.2 guarantee that $m_{p_{j},p_{i}}$ and $m_{p_{i},p_{k}}$ are in $S^{-}(p_{j},p_{i})$ and $S^{-}(p_{i},p_{k})$ respectively.
4d

Assume that Condition 4d was satisfied before the addition of $p_{i}$ to $P$ . We need to ensure that, after $p_{i}$ is added to $P$ , the condition still holds. Note that $p_{i}$ is selected to lie below $C(P)$ . As noted earlier, for any pair of points $\{p,q\}\in P$ , the portion of $B_{m_{p,q}}$ below the line determined by $\{p,q\}$ is completely contained in $S^{-}(p,q)$ . So for each pending pair $\{p,q\}$ in $C(P)$ , the portion of $B_{m_{p,q}}$ below $C(P)$ is disjoint from the portion of $B_{m_{p^{\prime},q^{\prime}}}$ below $C(P)$ for any other pending pair $\{p^{\prime},q^{\prime}\}$ in $C(P)$ . Thus when $p_{i}$ is added to $P$ , it will not lie in $B_{m_{p,q}}$ for any pending pair $\{p,q\}$ (other than, perhaps, $\{p_{j},p_{i}\}$ or $\{p_{i},p_{k}\}$ ), and so the neighborhoods for those pending pairs are unchanged. But by Section 3.2, $N_{P}(m_{p_{j},p_{i}})=\{p_{j},p_{i}\}$ and $N_{P}(m_{p_{i},p_{k}})=\{p_{i},p_{k}\}$ , so Condition 4d is satisfied.

$\hfill\blacktriangleleft$

Figure 2 depicts a border parabola drawing constructed with the procedure described in the proof of Theorem 8.

It is worth remarking that Theorem 8 extends a previous result by Aronov, Dulieu, and Hurtado [2] about the witness Gabriel drawability of trees. We also note that the witness Gabriel drawings of trees computed with the algorithm in [2] are neither linearly nor convexly separable.

4 Linearly Separable Triangle-free Witness Gabriel Drawings

As proved in the previous section, any graph that admits a border parabola drawing also admits a linearly separable witness Gabriel Drawing. In this section we will show that, for the family of triangle-free graphs, the converse is also true.

Lemma 9.

Let $\Gamma(P,W)$ be a witness Gabriel drawing, and let $\{p_{1},p_{2},q_{1},q_{2}\}\subseteq P$ be four distinct points such that

$\blacksquare$

$\{p_{1},p_{2}\}$ and $\{q_{1},q_{2}\}$ are crossing edges of $\Gamma(P,W)$ , and
$\blacksquare$

$\{p_{1},q_{1}\}$ and $\{p_{2},q_{2}\}$ are non-edges of $\Gamma(P,W)$ .

Then for any witnesses $\{w_{1},w_{2}\}\subseteq W$ for $\{p_{1},q_{1}\}$ and $\{p_{2},q_{2}\}$ respectively, the segment $\overline{w_{1}w_{2}}$ crosses edges $\{p_{1},p_{2}\}$ and $\{q_{1},q_{2}\}$ .

Proof.

Note that for the hypotheses of the lemma to be satisfied, it cannot be that an endpoint of one of the two edges lies on the other edge, since then the Gabriel disk of one of the non-edges would lie inside the Gabriel disk of one of the edges, making witness placement impossible. Thus the intersection point of the edges is in the interior of each edge.

Let $L_{1}$ be the line through $\{p_{1},q_{2}\}$ , $L_{2}$ be the line through $\{p_{2},q_{1}\}$ , and, if the lines are not parallel, let $c$ be their intersection point. By applying a suitable rotation, translation, and/or reflection, we can assume, w.l.o.g., that

$\blacksquare$

$L_{1}$ and $L_{2}$ are parallel with slope $0$ and are equidistant from the $x$ -axis, or $c$ lies at the origin and $L_{1}$ and $L_{2}$ have equal but oppositely signed slopes with all of $\{p_{1},p_{2},q_{1},q_{2}\}$ appearing to the left of $c$ ,
$\blacksquare$

$\{p_{1},p_{2},q_{1},q_{2}\}$ all lie on or above $L_{1}$ ,
$\blacksquare$

$p_{1}$ lies to the left of $q_{2}$ on $L_{1}$ , and so $q_{1}$ lies to the left of $p_{2}$ on $L_{2}$ ,

Let $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure8.pdf}}}}}[% p_{1},p_{2}]$ , $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure9.pdf}}}}}[% q_{1},q_{2}]$ , $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure10.pdf}}}}}% [p_{1},q_{1}]$ , and $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure11.pdf}}}}}% [p_{2},q_{2}]$ be the Gabriel disks of the two edges and two non-edges. By Section 2, each of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure12.pdf}}}}}% [p_{1},p_{2}]$ , $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure13.pdf}}}}}% [q_{1},q_{2}]$ intersect each of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure14.pdf}}}}}% [p_{1},q_{1}]$ , $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure15.pdf}}}}}% [p_{2},q_{2}]$ at two points and all eight such points of intersection lie on $L_{1}$ and $L_{2}$ . Four of the eight points are $\{p_{1},p_{2},q_{1},q_{2}\}$ ; denote the other four by $\{P_{1},P_{2},Q_{1},Q_{2}\}$ as follows: If $r\in\{p_{1},p_{2},q_{1},q_{2}\}$ , then $R$ denotes the other point of intersection of the two Gabriel disks that intersect at $r$ . Note that if $r\in\{p_{1},p_{2},q_{1},q_{2}\}$ lies on $L_{i}$ , for $1=1,2$ , then $R$ lies on $L_{3-i}$ . Figure 4 and 5 show the two possible configurations.

Note that since $p_{1}$ is to the left of $q_{2}$ on $L_{1}$ , $P_{1}$ must be to the left of $Q_{2}$ on $L_{2}$ ; similarly $Q_{1}$ must be to the left of $P_{2}$ on $L_{1}$ , since $q_{1}$ is to the left of $p_{2}$ on $L_{2}$ .

Figure 4: Illustration for Lemma 4 – parallel case.

Consider first the case where $L_{1}$ and $L_{2}$ are parallel and consider $L_{2}$ and the region above it. Now consider the portions of the Gabriel disks for the two edges that lie above $L_{2}$ . One portion connects $q_{1}$ to $Q_{2}$ and the other connects $p_{2}$ to $P_{1}$ . But since $q_{1}$ must be to the left of $p_{2}$ and $P_{1}$ must be to the left of $Q_{2}$ , the projections of those portions onto $L_{2}$ intersect and so either the portions cross or one is contained below the other. Since all of the eight intersection points of the four Gabriel disks lie on $L_{1}$ and $L_{2}$ either every point on the portions of the Gabriel disks of the two non-edges lying above $L_{2}$ lie below some point on a portion of one (or both) of the Gabriel disks for the two edges, or none do. But near the left-most of the four intersection points on $L_{2}$ ( $q_{1}$ in Figure 4), the portion of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure16.pdf}}}}}% [q_{1},q_{2}]$ above $L_{2}$ contains the portion of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure17.pdf}}}}}% [q_{1},p_{1}]$ above $L_{2}$ . Similarly, near the right-most of the four intersection points on $L_{2}$ ( $p_{2}$ in Figure 4), the portion of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure18.pdf}}}}}% [p_{2},p_{1}]$ above $L_{2}$ contains the portion of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure19.pdf}}}}}% [p_{2},q_{2}]$ above $L_{2}$ . Thus no portion of either of the Gabriel disks for the non-edges lies both above $L_{2}$ and outside the union of the Gabriel disks for the two edges.

A similar argument holds for the region below $L_{1}$ . Therefore any witnesses for $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure20.pdf}}}}}% [p_{1},q_{1}]$ and $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure21.pdf}}}}}% [p_{2},q_{2}]$ must lie in the horizontal strip between $L_{1}$ and $L_{2}$ . Note now that the entire quadrilateral bounded by $\{p_{1},p_{2},q_{1},q_{2}\}$ is contained in the union of the Gabriel disks of the two edges. Note also that the only points to the right of that quadrilateral and between $L_{1}$ and $L_{2}$ that disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure22.pdf}}}}}% [q_{1},p_{1}]$ can contain are also contained in $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure23.pdf}}}}}% [p_{1},p_{2}]\cup\mathbin{\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.600% 04pt\hbox{{\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure2% 4.pdf}}}}}[q_{1},q_{2}]$ : for any point $p^{\prime}$ that lies in this region, the angle $q_{1}p^{\prime}q_{2}$ is larger than the angle $q_{1}p^{\prime}p_{1}$ , so if $p^{\prime}$ lies in $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure25.pdf}}}}}% [q_{1},p_{1}]$ , then it also lies in $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure26.pdf}}}}}% [q_{1}q_{2}]$ . Similarly, the only points to the left of that quadrilateral and between $L_{1}$ and $L_{2}$ that disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure27.pdf}}}}}% [p_{2},q_{2}]$ can contain are also contained in $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure28.pdf}}}}}% [p_{1},p_{2}]\cup\mathbin{\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.600% 04pt\hbox{{\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure2% 9.pdf}}}}}[q_{1},q_{2}]$ . Thus a witness for $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure30.pdf}}}}}% [q_{1},p_{1}]$ must lie in the strip between $L_{1}$ and $L_{2}$ to the left of the quadrilateral and a witness for $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure31.pdf}}}}}% [q_{2},p_{2}]$ must lie in the strip between $L_{1}$ and $L_{2}$ to the right of the quadrilateral, implying that the segment between them crosses both $\{p_{1},p_{2}\}$ and $\{q_{1},q_{2}\}$ .

The proof in the case that $L_{1}$ and $L_{2}$ intersect is similar but slightly more involved. Instead of three regions of interest (below $L_{1}$ , between $L_{1}$ and $L_{2}$ , and above $L_{2}$ ), there are now four regions that we call the north, east, south, and west regions:

$\blacksquare$

north: the intersection of the regions above both $L_{1}$ and $L_{2}$ ,
$\blacksquare$

south: the intersection of the regions below both $L_{1}$ and $L_{2}$ ,
$\blacksquare$

west: the intersection of the region above $L_{1}$ and below $L_{2}$ , and
$\blacksquare$

east: the intersection of the region below $L_{1}$ and above $L_{2}$ .

Note that by construction, $\{p_{1},p_{2},q_{1},q_{2}\}$ are contained in the west region.

Figure 5: Illustration for Lemma 4 – skew case.

The analogous proof for this case uses the following observations:

$\blacksquare$

Any point within either of the Gabriel disks for the two non-edges that lies in the north or south regions is also within the union of the Gabriel disks for the two edges. Thus any witnesses for the two non-edges must lie in the west and/or east regions.
$\blacksquare$

The Gabriel disks of the two edges completely contain the quadrilateral formed by $\{p_{1},p_{2},q_{1},q_{2}\}$ ,
$\blacksquare$

The only points to the left of that quadrilateral and within the west region that disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure32.pdf}}}}}% [q_{2},p_{2}]$ can contain are also contained in $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure33.pdf}}}}}% [p_{1},p_{2}]\cup\mathbin{\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.600% 04pt\hbox{{\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure3% 4.pdf}}}}}[q_{1},q_{2}]$ .

However, it is not always the case that the disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure35.pdf}}}}}% [p_{1},q_{1}]$ does not contain any points to the right of that quadrilateral. There are two situations, depending upon whether $c$ , the intersection point of $L_{1}$ and $L_{2}$ , lies inside the four Gabriel disks or not. (It either lies in all four of the disks if $\angle q_{1}cq_{2}=\angle p_{1}cp_{2}\geq\pi/2$ or in none of them if not.) If $c$ lies outside of the four disks, then, in fact, the only points to the right of that quadrilateral and within the west region that disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure36.pdf}}}}}% [p_{1},q_{1}]$ can contain are also contained in $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure37.pdf}}}}}% [p_{1},p_{2}]\cup\mathbin{\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.600% 04pt\hbox{{\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure3% 8.pdf}}}}}[q_{1},q_{2}]$ . Moreover, in this case, neither of the Gabriel disks of the non-edges intersects the east region, and so witnesses for the two non-edges must both lie in the west region, but on opposite sides of the quadrilateral. Thus the segment between them will cross both $\{p_{1},p_{2}\}$ and $\{q_{1},q_{2}\}$ .

If $c$ lies inside the four Gabriel disks, then the portion of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure39.pdf}}}}}% [q_{2},p_{2}]$ that lies in the east region (and, in fact, all of $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure40.pdf}}}}}% [q_{2},p_{2}]$ ) will be contained in the union of the Gabriel disks of the two edges, so there will be no location at which a witness for $G[q_{2},p_{2}]$ can be placed. $\hfill\blacktriangleleft$

As a final ingredient, we will prove the following generalization of Property 2:

Property 4.

Let $\Gamma(P)$ be a linearly separable witness Gabriel drawing and $\{p_{1},p_{2},p_{3}\}\subset P$ be such that $x(p_{1})<x(p_{2})<x(p_{3})$ . If $\{p_{1},p_{3}\}$ forms an edge and $p_{2}$ lies above $\overline{p_{1}p_{3}}$ , then $\{p_{1},p_{2}\}$ and $\{p_{2},p_{3}\}$ also form edges.

Proof.

It suffices to note that the portion of the Gabriel disk $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure41.pdf}}}}}% [p_{1},p_{3}]$ below segment $\overline{p_{1}p_{3}}$ contains the portions of the Gabriel disks $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure42.pdf}}}}}% [p_{1},p_{2}]$ and $\mathbin{\immediate\immediate\immediate\immediate\immediate\immediate% \immediate\immediate\immediate\immediate\immediate\hbox{\lower 1.60004pt\hbox{% {\includegraphics{}{}{dagpub-tikzpictures/p013-Haase.latexml-figure43.pdf}}}}}% [p_{2},p_{3}]$ that lie below $\overline{p_{1}p_{3}}$ . $\hfill\blacktriangleleft$

We are now ready to state the main result of this section.

Theorem 10.

The following statements are equivalent for a triangle-free graph $G$ :

$\blacksquare$

$G$ is outerplanar
$\blacksquare$

$G$ admits a linearly separable witness Gabriel drawing
$\blacksquare$

$G$ admits a border parabola drawing.

Proof.

By Theorem 8, every outerplanar graph admits a border parabola drawing, and by definition every border parabola drawing is also a linearly separable witness Gabriel drawing. To show the equivalency, we still have to argue that, if a triangle-free graph admits a linearly separable witness Gabriel drawing, then it must be outerplanar.

An immediate consequence of Lemma 4 is that if $\Gamma(P,W)$ is a linearly separable witness Gabriel drawing, then $P$ cannot contain four points satisfying the hypotheses of the lemma: $P$ and $W$ are contained in disjoint half-planes and so no segment between two points in $P$ can cross a segment between two points in $W$ . In particular, if $\Gamma(P,W)$ is a linearly separable witness Gabriel drawing of a triangle-free graph, then $\Gamma(P,W)$ must be a planar drawing, since any pair of crossing edges would satisfy the hypotheses of Section 4. Moreover, no point of $P$ in such a drawing could lie vertically above any edge, since, otherwise, by Property 4, the drawing would contain a triangle, and so the drawing must, in fact, be outerplanar. $\hfill\blacktriangleleft$

We recall that results of [13, 14] show that the complete bipartite graphs admitting linearly separable witness Gabriel drawings are exactly those not containing $K_{2,3}$ as an induced subgraph. Following a characterization of triangle-free outerplanar graphs by Syslo [20], Theorem 10 extends these results showing that any triangle-free graph has a linearly separable witness Gabriel drawing if and only if it does not have $K_{2,3}$ as a minor.

5 Convexly Separable Witness Gabriel Drawings

A witness Gabriel drawing $\Gamma$ is said to be convexly separable if none of its witnesses lie within the interior of the convex hull of $\Gamma$ . Clearly, if a family of graphs admits linearly separable witness Gabriel drawings, then it also admits convexly separable ones. This holds, for example, for outerplanar graphs (see Theorem 8). However, two natural questions arise: (i) If a graph admits a convexly separable witness Gabriel drawing, does it always admit a linearly separable one? (ii) Are there graphs that are witness Gabriel drawable, but for which all such drawings must be convexly separable?

In this section, we answer the first question negatively and the second affirmatively by constructing witness Gabriel drawable graphs that require convex separability in any witness Gabriel drawing, but for which linear separability is not possible.

Lemma 11.

Every $K_{m,n}$ such that $m\geq 2$ and $n\geq 2$ admits a witness Gabriel drawing. Also, if $n>2$ any such drawing must be convexly separable but cannot be linearly separable.

Proof.

Every $K_{m,n}$ is witness Gabriel drawable by Theorem 5 of [2]. Also, for any $n>2$ $K_{m,n}$ contains $K_{2,3}$ as a subgraph and hence, by Theorem 10, it does not admit a linearly separable witness Gabriel drawing. It remains to show that every witness Gabriel drawing of $K_{m,n}$ is convexly separable. We color red every vertex of one partition set and blue every vertex of the other partition set of $K_{m,n}$ .

Let $\Gamma$ be a witness Gabriel drawing of $K_{m,n}$ and assume that there is a witness $w$ in the interior of the convex hull and let $u v$ be an edge of $K_{m,n}$ such that $u$ is a red vertex and $v$ is a blue vertex. Consider the line $L_{1}$ passing through $u$ and $w$ and the line $L_{2}$ passing through $v$ and $w$ . Lines $L_{1}$ and $L_{2}$ divide the plane into four wedges each having $w$ as their apex. We call these wedges the top wedge, bottom wedge, left wedge, and right wedge of $w$ , respectively. The top (left) wedge of $w$ is opposite to its bottom (right) wedge. We assume without loss of generality that edge $u v$ is in the right wedge of $w$ . See also Figure 6.

(a)

(b)

(c)

Figure 6: Illustration for the proof of Section 5.

Observe that no vertex $z$ of $\Gamma$ can be in the left wedge of $w$ . Namely, depending on its color, vertex $z$ would be adjacent to either $u$ or $v$ and we would have that $w$ is a point of the triangle whose corners are $u$ , $v$ , and $z$ , violating Section 2. Also, no edge $z t$ of the convex hull of $\Gamma$ can cross the left wedge of $w$ : If $z$ and $t$ have the same color, let $s$ be whichever of $u$ and $v$ has the other color. Now $\triangle[z,t,s]$ contains $w$ , violating Section 2. If $z$ and $t$ have different colors, they form an edge of $\Gamma$ and $\triangle[z,t,u]$ contains $w$ , which again violates Section 2.

Since no vertex and no edge of the convex hull of $\Gamma$ can intersect the left wedge of $w$ , it follows that $w$ is not in the interior of the convex hull of $\Gamma$ . $\hfill\blacktriangleleft$

Figure 7 shows a convexly separable witness Gabriel drawing of $K_{3,3}$ .

Figure 7: A witness Gabriel drawing of

K_{3,3}

.

The graphs of Section 5 are triangle-free and dense. We now prove a similar result for a planar triangulation consisting of just nine vertices.

Let $C=\{r,g,b\}$ and $I=\{1,2,3\}$ . Then we define the graph $G_{9}$ to have vertex set $V=\{c_{i}:c\in C,i\in I\}$ and edge set $E=\{\{r_{i},r_{j}\},\{b_{i},b_{j}\},\{g_{i},g_{j}\},\{b_{i},r_{j}\},\{b_{i},g_% {j}\}:1\leq i,j\leq 3,i\not=j\}$ . Note that $G_{9}$ can also be described as the complete graph on $V$ minus all edges $\{r_{i},g_{j}\},i,j\in I$ and $\{c_{i},c^{\prime}_{i}\},c,c^{\prime}\in C,i\in I$ ; see Figure 8(a). One can also obtain the graph $G_{9}$ by taking two octahedra and gluing them together at a triangular face. The vertex $v=c_{i}\in V$ , $c\in C,i\in I$ , is said to have color $c(v)=c$ and index $i(v)=i$ ; the index set of $V^{\prime}\subseteq V$ is given by $I(V^{\prime})=\{i(v):v\in V^{\prime}\}$ . We will refer to vertices having color $r$ as red vertices, color $b$ as blue vertices, and color $g$ as green vertices.

(a)

(b)

Figure 8: Graph

G_{9}

and a convexly separable witness Gabriel drawing of

G_{9}

.

By means of Section 4, Section 2 and Section 2, we can now prove the following.

Lemma 12.

Graph $G_{9}$ admits a witness Gabriel drawing. Also any such drawing must be convexly separable but cannot be linearly separable. Any proper subgraph of $G_{9}$ admits a linearly separable witness Gabriel drawing.

Proof.

It is possible to construct a convexly separable witness Gabriel drawing of $G_{9}$ . See Figure 8(b) for such an example.

We now show that no witness Gabriel drawing of $G_{9}$ can be linearly separable. Assume that there existed a linearly separable witness Gabriel Drawing $\Gamma$ of $G_{9}$ . By Section 4, Section 2, and Section 2, $\Gamma$ must be such that: (1) Any $V^{\prime}\subset V$ having $|I(V^{\prime})|<|I|=3$ induces a plane subgraph of $\Gamma$ . Note that since $V^{\prime}$ does not contain vertices of all three indices, the subgraph induced by $V^{\prime}$ contains no triangles. Thus, by Section 4, no two of its edges can cross. (2) Any induced $4$ -cycle of $\Gamma$ must form a convex quadrilateral: By (1), the $4$ -cycle forms a plane subgraph of $\Gamma$ . If it were not convex, one of the four vertices would be contained in the wedge formed by the other three and so, by Section 2, a diagonal would exist. (3) For any $\{i,j\}\subset I$ , the subgraph $G_{i,j}$ of $G_{9}$ induced by all vertices having indices in $\{i,j\}$ is a plane subgraph of $\Gamma$ consisting of the two convex quadrilaterals $R_{i,j}=\{b_{i},b_{j},r_{i},r_{j}\}$ and $G_{i,j}=\{b_{i},b_{j},g_{i},g_{j}\}$ . Further, these two quadrilaterals lie on opposite sides of the line $L_{i,j}$ determined by $\{b_{i},b_{j}\}$ . Both $R_{i,j}$ and $G_{i,j}$ , which we will call the red and green quadrilaterals, respectively, are induced 4-cycles of $G_{9}$ , and so by (2), each forms a convex quadrilateral in $\Gamma$ . If both were on the same side of $L_{i,j}$ , then either some edge of $R_{i,j}$ intersects some edge of $G_{i,j}$ , which is forbidden by (1), or one of the two quadrilaterals is contained in the other. Suppose that $R_{i,j}$ contains $G_{i,j}$ ; in particular $R_{i,j}$ contains the vertex $g_{i}$ . Now $b_{k}$ ( $k\not=i,j$ ) is adjacent to all of $\{b_{i},b_{j},r_{i},r_{j}\}$ and the triangles $\triangle(b_{k},b_{i},b_{j})$ , $\triangle(b_{k},b_{j},r_{i})$ , $\triangle(b_{k},r_{i},r_{j})$ , and $\triangle(b_{k},r_{j},b_{i})$ completely cover $R_{i,j}$ . This means, however, that one of the four triangles contains $g_{i}$ , violating Section 2, thus $R_{i,j}$ and $G_{i,j}$ must lie on opposite sides of $L_{i,j}$ .

Now consider the triangle $\triangle=\triangle(b_{1},b_{2},b_{3})$ and the three lines $L_{1,2},L_{2,3},L_{3,1}$ determined by it’s edges. We will refer to the half-plane of $L_{i,j}$ not containing $\triangle$ as the outer half-plane of $L_{i,j}$ . Since each outer half-plane $L_{i,j}$ contains one of $R_{i,j}$ and $G_{i,j}$ , then by the pigeon-hole principle, there are either at least two red quadrilaterals or two green quadrilaterals contained in their respective outer half-planes. So assume that, w.l.o.g., $R_{i,j}$ and $R_{i,k}$ are contained in the outer half-planes of $L_{i,j}$ and $L_{i,k}$ , respectively. Then, in particular, $r_{i}$ is contained in the intersection of these two outer half-planes. But this implies that $b_{i}$ is contained in the triangle $\triangle(r_{i},b_{j},b_{k})$ , violating Section 2. It follows that no witness Gabriel drawing of $G_{9}$ can be linearly separable.

With a similar reasoning as in the proof of Section 5, we now show that every witness Gabriel drawing $\Gamma$ of $G_{9}$ must be convexly separable. Suppose that there existed a witness $w$ in the interior of the convex hull of $\Gamma$ . Consider the smallest infinite wedge with apex $w$ containing the blue vertices of $\Gamma$ and extend the rays of the wedge to two lines that intersect at $w$ . These two lines define four wedges each of them having $w$ as an apex. We call these wedges the top wedge, bottom wedge, left wedge, and right wedge of $w$ , respectively. The top (left) wedge of $w$ is opposite to its bottom (right) wedge. We assume without loss of generality that the three blue vertices lie in the right wedge of $w$ and denote as $b_{i}$ and $b_{j}$ the two blue vertices along the boundary of this wedge; see Figure 9 for an illustration.

(a)

(b)

Figure 9: Illustration for the proof of Section 5: A witness Gabriel drawing

\Gamma

of

G_{9}

must be convexly separable.

We show that no edge of the convex hull of $\Gamma$ can intersect the left wedge of $w$ . First observe that there cannot be a vertex $z$ in the left wedge of $w$ : If vertex $z$ existed it would be adjacent to one of $\{b_{i},b_{j}\}$ and therefore $w$ would a point in the interior of the triangle whose corners are $b_{i}$ , $b_{j}$ , and $z$ , which contradicts Section 2. Furthermore, no edge $z t$ of the convex hull of $\Gamma$ can cross the left wedge of $w$ : Neither $z$ nor $t$ is a blue vertex; also $I(\{z,t\})$ has size at most $2$ , so there is some blue vertex $b$ adjacent to both $z$ and $t$ . The wedge formed by these three vertices contains $w$ , violating Section 2.

Since no edge of the convex hull of $\Gamma$ can intersect the left wedge of $w$ , it follows that $w$ is not in the interior of the convex hull of $\Gamma$ .

To conclude the proof, we need to show that every proper subgraph of $G_{9}$ has a linearly separable Gabriel drawing. It is sufficient to show that deleting any vertex of $G_{9}$ results in a graph that has a linearly separable witness Gabriel drawing. Figures 10 and 11 depict linearly separable witness Gabriel drawings (and exact coordinates) of $G_{9}$ minus a green vertex and of $G_{9}$ minus a blue vertex, respectively. $\hfill\blacktriangleleft$

Figure 8(b) depicts a convexly separable witness Gabriel drawing of $G_{9}$ , while Figures 10 and 11 depict linearly separable witness Gabriel drawings and exact coordinate of $G_{9}$ minus a green vertex and of $G_{9}$ minus a blue vertex, respectively. Section 5 complements Section 5 by providing an example which is a triangulated planar graph.

If we denote as $\cal{CSWGD}$ the set of those witness Gabriel drawable graphs whose witness Gabriel drawings must be convexly separable, and as $\cal{LSWGD}$ the set of those witness Gabriel drawable graphs that admit a linearly separable witness Gabriel drawing, then the results of this section can be summarized as follows.

Theorem 13.

$\cal{LSWGD}\subsetneq\cal{CSWGD}$ . Also, $\cal{CSWGD}\setminus\cal{LSWGD}$ contains both bipartite graphs and planar triangulations.

Vertex	$g_{1}$	$g_{2}$	$g_{3}$	$b_{1}$	$b_{3}$	$r_{1}$	$r_{2}$	$r_{3}$	$w_{1}$	$w_{2}$	$w_{3}$
$x$	$116$	$93$	$98$	$71$	$8$	$33$	$44$	$51$	$18$	$60$	$95$
$y$	$29$	$15$	$7$	$12$	$74$	$6$	$14$	$3$	$-1$	$-8$	$-2$

Figure 10: Coordinates of the vertices and witnesses in a linearly separable witness Gabriel drawing of

G_{9}

minus a blue vertex.

Vertex	$g_{1}$	$g_{2}$	$b_{1}$	$b_{2}$	$b_{3}$	$r_{1}$	$r_{2}$	$r_{3}$	$w_{1}$	$w_{2}$	$w_{3}$	$w_{4}$
$x$	$0$	$126$	$116$	$9$	$123$	$37$	$87$	$58$	$8$	$17$	$106$	$119$
$y$	$38$	$24$	$113$	$18$	$44$	$4$	$4$	$1$	$-1$	$-13$	$-17$	$-3$

Figure 11: Drawing and exact coordinates of the vertices and witnesses in a linearly separable witness Gabriel drawing of

G_{9}

minus a green vertex.

6 Concluding Remarks and Open Problems

In this paper we have studied witness Gabriel drawings where the sets of vertices and the set of witnesses are either linearly or convexly separable. We showed that every outerplanar graph admits a linearly separable witness Gabriel drawing. We remark that the witness Gabriel drawability of outerplanar graphs was known only for trees and, in addition, the known construction was not giving rise to separable realizations. We then characterized the triangle-free graphs that admit a linearly separable witness Gabriel drawing. Finally we proved that the family of linearly separable witness Gabriel drawable graphs is a proper subset of the convexly separable ones.

Several open problems naturally arise from our results. We conclude the paper by listing some of those that, in our opinion, are among the most interesting.

$\blacksquare$

Further investigate the relationship between border parabola graphs and linearly separable witness Gabriel drawable graphs. Specifically, are there graphs that admit a linearly separable Gabriel drawing but do not have a border parabola drawing?
$\blacksquare$

Extend the characterization of Theorem 10 to graphs that have $3$ -cycles.
$\blacksquare$

Characterize the convexly separable witness Gabriel drawings.
$\blacksquare$

Finally, an immediate consequence of Section 5 is that there are two planar triangulations (namely two copies of $G_{9}$ ) which do not admit a mutual witness Gabriel drawing. A mutual witness Gabriel drawing consists of a pair of witness Gabriel drawings where the vertex set of one drawing acts as the witness set for the other and vice versa. Clearly, if every witness Gabriel drawing of $G_{9}$ is convexly separable, any mutual witness Gabriel drawing of two copies of $G_{9}$ should be linearly separable, which is however impossible by Section 5. It would be interesting to further study pairs of planar graphs that admit or do not admit a mutual witness Gabriel drawing. Results in this direction are known for pairs of isomorphic trees and for bipartite graphs [9, 13, 14].

References

[1] Boris Aronov, Muriel Dulieu, and Ferran Hurtado. Witness (Delaunay) graphs. Comput. Geom., 44(6-7):329–344, 2011. doi:10.1016/j.comgeo.2011.01.001.
[2] Boris Aronov, Muriel Dulieu, and Ferran Hurtado. Witness Gabriel graphs. Comput. Geom., 46(7):894–908, 2013. doi:10.1016/J.COMGEO.2011.06.004.
[3] Boris Aronov, Muriel Dulieu, and Ferran Hurtado. Witness rectangle graphs. Graphs Comb., 30(4):827–846, 2014. doi:10.1007/s00373-013-1316-x.
[4] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999.
[5] Miguel Á. Carreira-Perpiñán and Richard S. Zemel. Proximity graphs for clustering and manifold learning. In L. Saul, Y. Weiss, and L. Bottou, editors, 17th Annual Conference on Neural Information Processing Systems (NIPS 2004), volume 17, pages 225–232. MIT Press, 2004. URL: https://proceedings.neurips.cc/paper/2004/hash/dcda54e29207294d8e7e1b537338b1c0-Abstract.html.
[6] Peter Eades, Seok-Hee Hong, Karsten Klein, and An Nguyen. Shape-based quality metrics for large graph visualization. In Emilio Di Giacomo and Anna Lubiw, editors, 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), volume 9411 of LNCS, pages 502–514. Springer, 2015. doi:10.1007/978-3-319-27261-0_41.
[7] Peter Eades, Seok-Hee Hong, An Nguyen, and Karsten Klein. Shape-based quality metrics for large graph visualization. J. Graph Algorithms Appl., 21(1):29–53, 2017. doi:10.7155/jgaa.00405.
[8] K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259–278, 1969. doi:10.2307/2412323.
[9] Carolina Haase, Philipp Kindermann, William J. Lenhart, and Giuseppe Liotta. Mutual witness proximity drawings of isomorphic trees. In Michael A. Bekos and Markus Chimani, editors, 31st International Symposium on Graph Drawing and Network Visualization (GD 2023), volume 14465 of LNCS, pages 304–319. Springer, 2023. doi:10.1007/978-3-031-49272-3_21.
[10] Seok-Hee Hong and Patrick Eades. $\beta$ -skeleton shape-based metrics for large and complex graph drawings. In 17th IEEE Pacific Visualization Conference (PacificVis 2024), pages 277–282. IEEE, 2024. doi:10.1109/PACIFICVIS60374.2024.00038.
[11] Seok-Hee Hong, Amyra Meidiana, James Wood, Juan Pablo Ataides, Peter Eades, and Kunsoo Park. dGG, dRNG, DSC: New degree-based shape-based faithfulness metrics for large and complex graph visualization. In 15th IEEE Pacific Visualization Symposium (PacificVis 2022), pages 51–60. IEEE, 2022. doi:10.1109/PACIFICVIS53943.2022.00014.
[12] Manabu Ichino and Jack Sklansky. The relative neighborhood graph for mixed feature variables. Pattern Recognit., 18(2):161–167, 1985. doi:10.1016/0031-3203(85)90040-8.
[13] William J. Lenhart and Giuseppe Liotta. Mutual witness Gabriel drawings of complete bipartite graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), volume 13764 of LNCS, pages 25–39. Springer, 2022. doi:10.1007/978-3-031-22203-0_3.
[14] William J. Lenhart and Giuseppe Liotta. Mutual witness Gabriel drawings of complete bipartite graphs. Theor. Comput. Sci., 974:114115, 2023. doi:10.1016/J.TCS.2023.114115.
[15] Giuseppe Liotta. Proximity drawings. In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 115–154. Chapman and Hall/CRC, 2013. URL: https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/proximity.pdf.
[16] Luke Mathieson and Pablo Moscato. An Introduction to Proximity Graphs, pages 213–233. Springer International Publishing, Cham, 2019. doi:10.1007/978-3-030-06222-4_4.
[17] Amyra Meidiana, Seok-Hee Hong, and Peter Eades. Shape-faithful graph drawings. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), volume 13764 of LNCS, pages 93–108. Springer, 2022. doi:10.1007/978-3-031-22203-0_8.
[18] Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Second Edition. Wiley Series in Probability and Mathematical Statistics. Wiley, 2000. doi:10.1002/9780470317013.
[19] Joseph O’Rourke and Godfried T. Toussaint. Pattern recognition. In Jacob E. Goodman, Joseph O’Rourke, and Csaba Toth, editors, Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall/CRC, 2017. URL: http://www.csun.edu/˜ctoth/Handbook/chap54.pdf.
[20] Maciej M. Syslo. Characterizations of outerplanar graphs. Discret. Math., 26(1):47–53, 1979. doi:10.1016/0012-365X(79)90060-8.
[21] Godfried T. Toussaint and Constantin Berzan. Proximity-graph instance-based learning, support vector machines, and high dimensionality: An empirical comparison. In Petra Perner, editor, 8th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM 2012), volume 7376 of LNCS, pages 222–236. Springer, 2012. doi:10.1007/978-3-642-31537-4_18.

[bib.bib1] [1] Boris Aronov, Muriel Dulieu, and Ferran Hurtado. Witness (Delaunay) graphs. Comput. Geom., 44(6-7):329–344, 2011. doi:10.1016/j.comgeo.2011.01.001.

[bib.bib2] [2] Boris Aronov, Muriel Dulieu, and Ferran Hurtado. Witness Gabriel graphs. Comput. Geom., 46(7):894–908, 2013. doi:10.1016/J.COMGEO.2011.06.004.

[bib.bib3] [3] Boris Aronov, Muriel Dulieu, and Ferran Hurtado. Witness rectangle graphs. Graphs Comb., 30(4):827–846, 2014. doi:10.1007/s00373-013-1316-x.

[bib.bib4] [4] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999.

[bib.bib5] [5] Miguel Á. Carreira-Perpiñán and Richard S. Zemel. Proximity graphs for clustering and manifold learning. In L. Saul, Y. Weiss, and L. Bottou, editors, 17th Annual Conference on Neural Information Processing Systems (NIPS 2004), volume 17, pages 225–232. MIT Press, 2004. URL: https://proceedings.neurips.cc/paper/2004/hash/dcda54e29207294d8e7e1b537338b1c0-Abstract.html.

[bib.bib6] [6] Peter Eades, Seok-Hee Hong, Karsten Klein, and An Nguyen. Shape-based quality metrics for large graph visualization. In Emilio Di Giacomo and Anna Lubiw, editors, 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), volume 9411 of LNCS, pages 502–514. Springer, 2015. doi:10.1007/978-3-319-27261-0_41.

[bib.bib7] [7] Peter Eades, Seok-Hee Hong, An Nguyen, and Karsten Klein. Shape-based quality metrics for large graph visualization. J. Graph Algorithms Appl., 21(1):29–53, 2017. doi:10.7155/jgaa.00405.

[bib.bib8] [8] K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259–278, 1969. doi:10.2307/2412323.

[bib.bib9] [9] Carolina Haase, Philipp Kindermann, William J. Lenhart, and Giuseppe Liotta. Mutual witness proximity drawings of isomorphic trees. In Michael A. Bekos and Markus Chimani, editors, 31st International Symposium on Graph Drawing and Network Visualization (GD 2023), volume 14465 of LNCS, pages 304–319. Springer, 2023. doi:10.1007/978-3-031-49272-3_21.

[bib.bib10] [10] Seok-Hee Hong and Patrick Eades. $\beta$ -skeleton shape-based metrics for large and complex graph drawings. In 17th IEEE Pacific Visualization Conference (PacificVis 2024), pages 277–282. IEEE, 2024. doi:10.1109/PACIFICVIS60374.2024.00038.

[bib.bib11] [11] Seok-Hee Hong, Amyra Meidiana, James Wood, Juan Pablo Ataides, Peter Eades, and Kunsoo Park. dGG, dRNG, DSC: New degree-based shape-based faithfulness metrics for large and complex graph visualization. In 15th IEEE Pacific Visualization Symposium (PacificVis 2022), pages 51–60. IEEE, 2022. doi:10.1109/PACIFICVIS53943.2022.00014.

[bib.bib12] [12] Manabu Ichino and Jack Sklansky. The relative neighborhood graph for mixed feature variables. Pattern Recognit., 18(2):161–167, 1985. doi:10.1016/0031-3203(85)90040-8.

[bib.bib13] [13] William J. Lenhart and Giuseppe Liotta. Mutual witness Gabriel drawings of complete bipartite graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), volume 13764 of LNCS, pages 25–39. Springer, 2022. doi:10.1007/978-3-031-22203-0_3.

[bib.bib14] [14] William J. Lenhart and Giuseppe Liotta. Mutual witness Gabriel drawings of complete bipartite graphs. Theor. Comput. Sci., 974:114115, 2023. doi:10.1016/J.TCS.2023.114115.

[bib.bib15] [15] Giuseppe Liotta. Proximity drawings. In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 115–154. Chapman and Hall/CRC, 2013. URL: https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/proximity.pdf.

[bib.bib16] [16] Luke Mathieson and Pablo Moscato. An Introduction to Proximity Graphs, pages 213–233. Springer International Publishing, Cham, 2019. doi:10.1007/978-3-030-06222-4_4.

[bib.bib17] [17] Amyra Meidiana, Seok-Hee Hong, and Peter Eades. Shape-faithful graph drawings. In Patrizio Angelini and Reinhard von Hanxleden, editors, 30th International Symposium on Graph Drawing and Network Visualization (GD 2022), volume 13764 of LNCS, pages 93–108. Springer, 2022. doi:10.1007/978-3-031-22203-0_8.

[bib.bib18] [18] Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Second Edition. Wiley Series in Probability and Mathematical Statistics. Wiley, 2000. doi:10.1002/9780470317013.

[bib.bib19] [19] Joseph O’Rourke and Godfried T. Toussaint. Pattern recognition. In Jacob E. Goodman, Joseph O’Rourke, and Csaba Toth, editors, Handbook of Discrete and Computational Geometry, Third Edition. Chapman and Hall/CRC, 2017. URL: http://www.csun.edu/˜ctoth/Handbook/chap54.pdf.

[bib.bib20] [20] Maciej M. Syslo. Characterizations of outerplanar graphs. Discret. Math., 26(1):47–53, 1979. doi:10.1016/0012-365X(79)90060-8.

[bib.bib21] [21] Godfried T. Toussaint and Constantin Berzan. Proximity-graph instance-based learning, support vector machines, and high dimensionality: An empirical comparison. In Petra Perner, editor, 8th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM 2012), volume 7376 of LNCS, pages 222–236. Springer, 2012. doi:10.1007/978-3-642-31537-4_18.