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 -