http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7109
Quasi-upward planarity (Articolo in rivista)
- Type
- Label
- Quasi-upward planarity (Articolo in rivista) (literal)
- Anno
- 2002-01-01T00:00:00+01:00 (literal)
- Alternative label
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Bertolazzi, P.; Di Battista, G.; Didimo, W. (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Note
- ISI Web of Science (WOS) (literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
- Paola Bertolazzi Istituto di Analisi dei Sistemi ed informatica
Giuseppe Di Battista, Diaprtimento di Automatica e Informatica, Universita' di Roma III
Walter Didimo, Dipartimento di Ingegneria Elettronica e dell'Informazione, Universita' di Perugia (literal)
- Titolo
- Quasi-upward planarity (literal)
- Abstract
- An upward planar drawing of a directed graph (digraph) is a planar drawing
such that all the edges are represented by curves monotonically increasing
in the vertical direction. In this paper we introduce and study the concept
of quasi-upward planarity.
Quasi-upward planarity allows us to extend the upward planarity theory to a
large class of digraphs including digraphs that also have
directed cycles. First, we characterize the digraphs that have a
quasi-upward planar drawing. Second, we give a polynomial time
algorithm for computing ``optimal'' quasi-upward planar drawings
within a given planar embedding. Further, we apply branch and bound
techniques to the problem of computing optimal quasi-upward planar
drawings, considering all possible planar embeddings. The paper
also contains experimental results about the proposed techniques. (literal)
- Prodotto di
- Autore CNR
- Insieme di parole chiave
Incoming links:
- Autore CNR di
- Prodotto
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
- Insieme di parole chiave di
