[an error occurred while processing this directive]

[an error occurred while processing this directive]

<h1>Maximum Pagenumber-k Subgraph Is NP-Complete</h1>

<p>Peter Jonsson and Marco Kuhlmann. Maximum Pagenumber-k Subgraph Is NP-Complete. <em>CoRR</em>, abs/1504.05908, 2015.</p>

<h2>Abstract</h2>

<p>Given a graph $G$ with a total order defined on its vertices, the Maximum Pagenumber-$k$ Subgraph Problem asks for a maximum subgraph $G'$ of $G$ such that $G'$ can be embedded into a $k$-book when the vertices are placed on the spine according to the specified total order. We show that this problem is NP-complete for $k &#8805; 2$.</p>

<h2>Links</h2>

<ul>
<li><a href="jonsson2015maximum.bib">Download a BibTeX entry for this publication</a></li>
<li><a href="http://arxiv.org/abs/1504.05908">http://arxiv.org/abs/1504.05908</a></li>
</ul>


[an error occurred while processing this directive]