<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs

A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article 01 Jan 1999Publisher:World Scientific Pub Co Pte LtdJournal:Journal of Graph Algorithms and Applications, volume 3, pages 31-62 (eissn: 1526-1719,

Authors: Takao Nishizeki; Md. Saidur Rahman; Shin-ichi Nakano;

doi: 10.1142/9789812777638_0017 , 10.7155/jgaa.00017

A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs

- Summary
- Subjects
- Metrics

tips_and_updates
Recommended

Abstract

Summary: An orthogonal drawing of a plane graph \(G\) is a drawing of \(G\) in which each edge is drawn as a sequence of alternate horizontal and vertical line segments. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best previously known algorithm takes time \(O(n^{7/4} \sqrt{\log n})\) for any plane graph with \(n\) vertices.

Related Organizations

Tohoku University
Japan

Keywords

Extremal problems in graph theory, plane graph, linear-time algorithm, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, orthogonal drawing, Planar graphs; geometric and topological aspects of graph theory

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	33
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%