The planar slope number of planar partial 3-trees of bounded degree

DOI10.1007/S00373-012-1157-ZzbMATH Open1268.05052arXiv1012.4137OpenAlexW2050138073MaRDI QIDQ354442FDOQ354442

Authors: Vít Jelínek, Eva Jelínková, Jan Kratochvíl, Bernard Lidický, Marek Tesař, Tomáš Vyskočil 

Publication date: 19 July 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree $Delta$. We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most $O(Delt{a}^5)$. In particular, we answer the question of Dujmovi'c et al. [Computational Geometry 38 (3), pp. 194--212 (2007)] whether there is a function $f$ such that plane maximal outerplanar graphs can be drawn using at most $f(Delta)$ slopes.

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

Recommendations

• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Planar and plane slope number of partial 2-trees
• Drawings of planar graphs with few slopes and segments

zbMATH Keywords

planar graphsgraph drawingplanar slope numberslopes

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Graph drawings with few slopes
• Drawings of planar graphs with few slopes and segments
• Bounded-degree graphs have arbitrarily large geometric thickness
• Bounded-degree graphs can have arbitrarily large slope numbers
• Drawing Cubic Graphs with the Four Basic Slopes
• Drawability of Complete Graphs Using a Minimal Slope Set
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Drawing Cubic Graphs with at Most Five Slopes
• Graph Drawing
• Geometric representation of cubic graphs with four directions

Cited In (21)

• Universal slope sets for 1-bend planar drawings
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Planar drawings with few slopes of Halin graphs and nested pseudotrees
• Drawings of planar graphs with few slopes and segments
• Planar drawings with few slopes of Halin graphs and nested pseudotrees
• Drawing subcubic planar graphs with four slopes and optimal angular resolution
• Planar and plane slope number of partial 2-trees
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
• Outerplanar graph drawings with few slopes
• Upward planar drawings with three and more slopes
• 1-bend upward planar slope number of SP-digraphs
• The Planar Slope Number of Subcubic Graphs
• Upward planar drawings with two slopes
• On the 3-tree core of plane graphs
• Upward Planar Drawings with Three and More Slopes
• Universal slope sets for upward planar drawings
• Trees and Co-trees with Bounded Degrees in Planar 3-connected Graphs
• 1-bend upward planar drawings of SP-digraphs
• On the complexity of the planar slope number problem
• Drawing partial 2-trees with few slopes

This page was built for publication: The planar slope number of planar partial 3-trees of bounded degree

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