At most single-bend embeddings of cubic graphs
type: Item
instance of: scholarly article
title: At most single-bend embeddings of cubic graphs
zbMATH Open document ID: 0808.05039
DOI: 10.1007/BF02662066
published in: Applied Mathematics. Series B (English Edition)
publication date: 1995-03-07T00:00:00Z
review text: A graph is said to be single-bend embeddable if it has an embedding in the plane for which every edge consists of at most two horizontal or vertical line segments. (A bend is the intersection point of two line segments, one horizontal and the other vertical, whose union represents one edge.) It is shown that every cubic connected planar graph except \(K_ 4\) is single-bend embeddable. An \(O(n)\) amortized time algorithm is given for drawing a single-bend embeddable cubic graph of order \(n\). It is shown that the minimum total number of bends for a single-bend embeddable cubic graph of order \(n\) is at most \(n/2 + 1\); the result is best possible. This study has relevance to VLSI design.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 57M15
zbMATH DE Number: 646765
zbMATH Keywords: single-bend embeddings
zbMATH Keywords: plane
zbMATH Keywords: bend
zbMATH Keywords: cubic graph
zbMATH Keywords: VLSI design
author: Yanpei Liu
author: Paola Marchioro
author: Rossella Petreschi
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Planar graphs: Theory and algorithms
cites work: Q3883524
cites work: Computing an st-numbering
cites work: Q5596083
cites work: Theoretical results on at most 1-bend embeddability of graphs
cites work: General theoretical results on rectilinear embeddability of graphs
cites work: Q5528475
cites work: Algorithms for drawing graphs: An annotated bibliography
full work available at URL: https://doi.org/10.1007/bf02662066
OpenAlex ID: W2054234829
description: scientific article; zbMATH DE number 646765