Straight line embeddings of rooted star forests in the plane
type: Item
instance of: scholarly article
title: Straight line embeddings of rooted star forests in the plane
zbMATH Open document ID: 0942.05017
DOI: 10.1016/S0166-218X(99)00191-2
author: Atsushi Kaneko
author: Mikio Kano
published in: Discrete Applied Mathematics
publication date: 2000-08-06T00:00:00Z
review text: Fáry's theorem asserts that any finite planar graph has a straight-line embedding in the plane (i.e., one in which the edges are represented by straight-line segments). The present work investigates the possibility of finding a straight-line embedding in which the vertices correspond to arbitrarily chosen points in the plane---it is known, for example, that any outerplanar graph with \(n\) vertices has a straight-line embedding in which the vertices correspond to any given set of \(n\) points in the plane in general position. The authors study this question for rooted star forests, that is, for forests whose components are all stars, and for which one vertex (called the ``root'') is distinguished from each component. They show: given any rooted star forest \(F\) with \(n\) vertices and \(c\) components, any set \(S\) of \(n\) points in the plane in general position and any subset \(R\) of \(c\) of these points, \(F\) has a straight-line embedding in the plane in which the vertices correspond to the points in \(S\) and the roots to the points in \(R\). A simple example shows that the hypothesis that each component be a star cannot be dropped, in general.
reviewed by: Carl Droms
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1428621
zbMATH Keywords: straight-line embedding
zbMATH Keywords: star forest
MaRDI profile type: Publication
cites work: How to draw a planar graph on a grid
cites work: Straight-line embeddings of two rooted trees in the plane
cites work: Balanced partitions of two sets of points in the plane
cites work: On a straight-line embedding problem of graphs
cites work: The rooted tree embedding problem into points in the plane
cites work: Q3138292
full work available at URL: s0166-218x(99)00191-2
OpenAlex ID: W1992416537
description: scientific article; zbMATH DE number 1428621