2026-07-25T18:33:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24999 2026-02-09T07:52:41Z ddc:004 open_access

Separability of Witness Gabriel Drawings Haase, Carolina Kindermann, Philipp Lenhart, William Liotta, Giuseppe Proximity Drawings Witness Gabriel Graphs Geometric Graph Theory A witness Gabriel drawing Γ is a straight-line drawing of a graph in which any two vertices of Γ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carolina Haase and Philipp Kindermann and William Lenhart and Giuseppe Liotta 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.13 urn:nbn:de:0030-drops-249998 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode