TY - GEN
T1 - Triangle-partitioning edges of planar graphs, toroidal graphs and k-planar graphs
AU - Gao, Jiawei
AU - Kloks, Ton
AU - Poon, Sheung Hung
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - We consider the question whether the edges of a graph can be partitioned into a set of triangles. We propose a linear-time algorithm to partition the edges of a planar graph into triangles. We also obtain a polynomial-time algorithm for toroidal graphs. On the other hand, we show that it is NP-complete for k-planar graphs, where k ≥ 8.
AB - We consider the question whether the edges of a graph can be partitioned into a set of triangles. We propose a linear-time algorithm to partition the edges of a planar graph into triangles. We also obtain a polynomial-time algorithm for toroidal graphs. On the other hand, we show that it is NP-complete for k-planar graphs, where k ≥ 8.
UR - http://www.scopus.com/inward/record.url?scp=84873861207&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36065-7_19
DO - 10.1007/978-3-642-36065-7_19
M3 - Conference contribution
AN - SCOPUS:84873861207
SN - 9783642360640
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 194
EP - 205
BT - WALCOM
T2 - 7th International Workshop on Algorithms and Computation, WALCOM 2013
Y2 - 14 February 2013 through 16 February 2013
ER -