Drawing plane graphs nicely
type: Item
instance of: scholarly article
title: Drawing plane graphs nicely
zbMATH Open document ID: 0545.68057
DOI: 10.1007/BF00264230
author: Norishige Chiba
author: Kazunori Onoguchi
author: Takao Nishizeki
published in: Acta Informatica
publication date: 1985-01-01T00:00:00Z
review text: This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph ''convex'' if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, procedures a pleasing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 3868634
zbMATH Keywords: efficient algorithms
zbMATH Keywords: drawing plane graphs
zbMATH Keywords: straight line segments without crossing lines
zbMATH Keywords: convex polygons
MaRDI profile type: Publication
cites work: A linear algorithm for embedding planar graphs using PQ-trees
cites work: Q3220608
cites work: Q5786239
cites work: Dividing a Graph into Triconnected Components
cites work: Efficient Planarity Testing
cites work: Generalized Nested Dissection
cites work: The complexity of drawing trees nicely
cites work: Planarity and duality of finite and infinite graphs
cites work: Convex Representations of Graphs
cites work: How to Draw a Graph
cites work: Pretty-printing of trees
cites work: Tidy Drawings of Trees
description: scientific article; zbMATH DE number 3868634