The complexity of upward drawings on spheres
type: Item
instance of: scholarly article
title: The complexity of upward drawings on spheres
zbMATH Open document ID: 0913.06001
DOI: 10.1023/A:1006095702164
author: S. Mehdi Hashemi
author: Ivan Rival
author: Andrzej Kisielewicz
published in: Order
publication date: 1999-03-07T00:00:00Z
review text: Usually, an ordered set is identified with its geometric representation, called its upward drawing, where the elements of the ordered set \(P\) are drawn on a surface, traditionally a plane, as disjoint small circles, arranged in such a way that for \(a, b\in P\), the circle corresponding to \(a\) is higher than the circle corresponding to \(b\) whenever \(a>b\) and an arc, monotonic with respect to a fixed direction, is drawn to join them just if \(a\) covers \(b\). An ordered set is said to be planar if it has an upward drawing in the plane in which no arcs cross, although they may meet at a vertex with which they are incident. A recent result due to \textit{A. Garg} and \textit{R. Tamassia} [Order 12, 109-133 (1995; Zbl 0836.68081)] states that upward planarity testing is NP-complete. The main result of this paper is that the decision problem whether an ordered set has an upward drawing on a sphere is NP-complete. The proof involves the investigation of the surface topology of ordered sets highlighting especially their saddle points. A simpler proof of Garg and Tamassia's theorem, based on an exact cover by 3-sets is given. Finally, three open problems are stated.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1228609
zbMATH Keywords: ordered set
zbMATH Keywords: upward drawing
zbMATH Keywords: sphere
zbMATH Keywords: saddle point
zbMATH Keywords: NP-complete problem
zbMATH Keywords: surface topology of ordered sets
MaRDI profile type: Publication
full work available at URL: a:1006095702164
OpenAlex ID: W206077490
Recommended article: Q4233443
Recommended article: Q4881858
Recommended article: Upward Planarity Testing via SAT
Recommended article: Upward planarity testing
Recommended article: Upward Planarity Testing: A Computational Study
Recommended article: Rolling Upward Planarity Testing of Strongly Connected Graphs
Recommended article: Upward planarity testing in practice: SAT formulations and comparative study
Recommended article: Building Blocks of Upward Planar Digraphs
Recommended article: On upward point set embeddability
Recommended article: Graph Drawing
description: scientific article; zbMATH DE number 1228609