Outerplanar graph drawings with few slopes

DOI10.1016/J.COMGEO.2014.01.003MaRDI QIDQ2444313zbMATH OpenOpenAlexFDO

Authors Kolja Knauer, Piotr Micek, Bartosz Walczak

Publication date 9 April 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.2548

zbMATH Keywords

outerplanar graphslope numberstraight-line drawing

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that $Delta-1$ edge slopes suffice for every outerplanar graph with maximum degree $Deltage4$. This improves on the previous bound of $O(Delt{a}^5)$, which was shown for planar partial 3-trees, a superclass of outerplanar graphs. The bound is tight: for every $Deltage4$ there is an outerplanar graph with maximum degree $Delta$ that requires at least $Delta-1$ distinct edge slopes in an outerplanar straight-line drawing.

Review text

A straight-line drawing of a graph \(G\) is a mapping of the vertices of \(G\) into distinct points of the plane and of the edges of \(G\) into straight-line segments connecting the points representing their end-vertices and passing through no other points representing vertices. The slope of an edge in a straight-line drawing is the family of all straight lines parallel to this edge. The slope number of a graph \(G\) is the smallest number \(s\) such that there is a straight-line drawing of \(G\) using \(s\) slopes. The main result of the paper is that for \(\Delta \leq 4\) every outerplanar graph with maximum degree at most \(\Delta\) has outerplanar slope number at most \(\Delta - 1\). The bound is tight because there is an outerplanar graph with maximum degree that requires this slope number.

Recommendations

• Drawing outer 1-planar graphs with few slopes
• Drawing outer 1-planar graphs with few slopes
• Drawings of planar graphs with few slopes and segments

Cites work

• Bemerkungen zum Vierfarbenproblem
• Bounded-degree graphs can have arbitrarily large slope numbers
• Bounded-degree graphs have arbitrarily large geometric thickness
• Drawability of Complete Graphs Using a Minimal Slope Set
• Drawing cubic graphs with at most five slopes
• Drawing Cubic Graphs with the Four Basic Slopes
• Drawings of planar graphs with few slopes and segments
• Geometric representation of cubic graphs with four directions
• Graph drawings with few slopes
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• The planar slope number of planar partial 3-trees of bounded degree

Cited in

(17)

• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Upward planar drawings with three and more slopes
• 1-bend upward planar slope number of SP-digraphs
• Universal slope sets for 1-bend planar drawings
• Drawing partial 2-trees with few slopes
• 1-bend upward planar drawings of SP-digraphs
• On the complexity of the planar slope number problem
• Upward planar drawings with two slopes
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Upward Planar Drawings with Three and More Slopes
• Drawing outer 1-planar graphs with few slopes
• Drawing outer 1-planar graphs with few slopes
• Level-planar drawings with few slopes
• Universal slope sets for upward planar drawings
• Level-planar drawings with few slopes
• Planar drawings with few slopes of Halin graphs and nested pseudotrees
• Planar drawings with few slopes of Halin graphs and nested pseudotrees

This page was built for publication: Outerplanar graph drawings with few slopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444313)