Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(1)
Polynomial Algorithm
Subscribe
Academic
Publications
Simple Realizability of Complete Abstract Topological Graphs in P
Simple Realizability of Complete Abstract Topological Graphs in P,10.1007/s004540109320x,Discrete & Computational Geometry,Jan Kyncl
Edit
Simple Realizability of Complete Abstract Topological Graphs in P
BibTex

RIS

RefWorks
Download
Jan Kyncl
An abstract topological graph (briefly an ATgraph) is a pair where G=(V,E) is a graph and is a set of pairs of its edges. An ATgraph A is simply realizable if G can be drawn in the plane in such a way that each pair of edges from crosses exactly once and no other pair crosses. We present a
polynomial algorithm
which decides whether a given complete ATgraph is simply realizable. On the other hand, we show that other similar realizability problems for (complete) ATgraphs are NPhard.
Journal:
Discrete & Computational Geometry  DCG
, vol. 45, no. 3, pp. 383399, 2011
DOI:
10.1007/s004540109320x
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(24)
On the crossing number of complete graphs
(
Citations: 36
)
Oswin Aichholzer
,
Franz Aurenhammer
,
Hannes Krasser
Conference:
Symposium on Computational Geometry  SOCG
, pp. 1924, 2002
Some algebraic and geometric computations in PSPACE
(
Citations: 218
)
John F. Canny
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 460467, 1988
Complete Graph Drawings Up to Triangle Mutations
(
Citations: 2
)
Emeric Gioan
Conference:
Workshop on GraphTheoretic Concepts in Computer Science  WG
, pp. 139150, 2005
Simultaneous Graph Embeddings with Fixed Edges
(
Citations: 15
)
Elisabeth Gassner
,
Michael Jünger
,
Merijam Percan
,
Marcus Schaefer
,
Michael Schulz
Conference:
Workshop on GraphTheoretic Concepts in Computer Science  WG
, pp. 325335, 2006
Proof of a conjecture of Burr, Grünbaum, and Sloane
(
Citations: 27
)
Jacob E. Goodman
Journal:
Discrete Mathematics  DM
, vol. 32, no. 1, pp. 2735, 1980