Minimum-segment convex drawings of 3-connected cubic plane graphs

Debajyoti Mondal (), Rahnuma Islam Nishat (), Sudip Biswas () and Md. Saidur Rahman ()
Additional contact information
Debajyoti Mondal: Bangladesh University of Engineering and Technology (BUET)
Rahnuma Islam Nishat: Bangladesh University of Engineering and Technology (BUET)
Sudip Biswas: Bangladesh University of Engineering and Technology (BUET)
Md. Saidur Rahman: Bangladesh University of Engineering and Technology (BUET)

Journal of Combinatorial Optimization, 2013, vol. 25, issue 3, No 6, 460-480

Abstract: Abstract A convex drawing of a plane graph G is a plane drawing of G, where each vertex is drawn as a point, each edge is drawn as a straight line segment and each face is drawn as a convex polygon. A maximal segment is a drawing of a maximal set of edges that form a straight line segment. A minimum-segment convex drawing of G is a convex drawing of G where the number of maximal segments is the minimum among all possible convex drawings of G. In this paper, we present a linear-time algorithm to obtain a minimum-segment convex drawing Γ of a 3-connected cubic plane graph G of n vertices, where the drawing is not a grid drawing. We also give a linear-time algorithm to obtain a convex grid drawing of G on an $(\frac{n}{2}+1)\times(\frac {n}{2}+1)$ grid with at most s n +1 maximal segments, where $s_{n}=\frac{n}{2}+3$ is the lower bound on the number of maximal segments in a convex drawing of G.

Keywords: Graph drawing; Convex drawing; Minimum-segment; Grid drawing; Cubic graph (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9390-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:25:y:2013:i:3:d:10.1007_s10878-011-9390-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9390-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().