Triangle-partitioning edges of planar graphs, toroidal graphs and k-planar graphs

Jiawei Gao, Ton Kloks, Sheung Hung Poon

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 7th International Workshop, WALCOM 2013, Proceedings
Pages194-205
Number of pages12
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event7th International Workshop on Algorithms and Computation, WALCOM 2013 - Kharagpur, India
Duration: 14 Feb 201316 Feb 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7748 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Workshop on Algorithms and Computation, WALCOM 2013
Country/TerritoryIndia
CityKharagpur
Period14/02/1316/02/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Triangle-partitioning edges of planar graphs, toroidal graphs and k-planar graphs'. Together they form a unique fingerprint.

Cite this