BitonicOrdering::BitonicOrdering(Graph& G, adjEntry adj_st_edge)
  : m_graph(G)
  , m_currLabel(0)
  , m_orderIndex(G,-1)
  , m_indexToNode(G.numberOfNodes())
  , m_tree(G, adj_st_edge->theEdge(), true)
{
    // set all tree nodes to non flipped
    m_flipped.init(m_tree.tree(), false);

    // s in the graph
    node s_G = adj_st_edge->theNode();
    node t_G = adj_st_edge->twinNode();

    // we label s here manually: set the label
    m_orderIndex[s_G] = m_currLabel++;
    // and update the other map
    m_indexToNode[m_orderIndex[s_G]] = s_G;

    // label everything else except t
    handleCase(m_tree.rootNode());

    // we label s here manually: set the label
    m_orderIndex[t_G] = m_currLabel++;
    // and update the other map
    m_indexToNode[m_orderIndex[t_G]] = t_G;

    // finally embedd G
    m_tree.embed(m_graph);
}

void CombinatorialEmbedding::moveBridge(adjEntry adjBridge, adjEntry adjBefore)
{
	OGDF_ASSERT(m_rightFace[adjBridge] == m_rightFace[adjBridge->twin()]);
	OGDF_ASSERT(m_rightFace[adjBridge] != m_rightFace[adjBefore]);

	face fOld = m_rightFace[adjBridge];
	face fNew = m_rightFace[adjBefore];

	adjEntry adjCand = adjBridge->faceCycleSucc();

	int sz = 0;
	adjEntry adj;
	for(adj = adjBridge->twin(); adj != adjCand; adj = adj->faceCycleSucc()) {
		if (fOld->entries.m_adjFirst == adj)
			fOld->entries.m_adjFirst = adjCand;
		m_rightFace[adj] = fNew;
		++sz;
	}

	fOld->m_size -= sz;
	fNew->m_size += sz;

	edge e = adjBridge->theEdge();
	if(e->source() == adjBridge->twinNode())
		m_pGraph->moveSource(e, adjBefore, after);
	else
		m_pGraph->moveTarget(e, adjBefore, after);

	OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
}

string print_arc_string(adjEntry a)
{
  sprintf(buf, "%d->%d", a->theNode()->index(), a->twinNode()->index());

  string res = buf;
  return res;
}

bool FeasibleUpwardPlanarSubgraph::constructMergeGraph(
	GraphCopy &M,
	adjEntry adj_orig,
	const List<edge> &orig_edges)
{
	CombinatorialEmbedding Beta(M);

	//set ext. face of Beta
	adjEntry ext_adj = M.copy(adj_orig->theEdge())->adjSource();
	Beta.setExternalFace(Beta.rightFace(ext_adj));

	FaceSinkGraph fsg(Beta, M.copy(adj_orig->theNode()));
	SList<node> aug_nodes;
	SList<edge> aug_edges;
	SList<face> fList;
	fsg.possibleExternalFaces(fList); // use this method to call the methode checkForest()
	node v_ext = fsg.faceNodeOf(Beta.externalFace());

	OGDF_ASSERT(v_ext != 0);

	fsg.stAugmentation(v_ext, M, aug_nodes, aug_edges);

	//add the deleted edges
	for(edge eOrig: orig_edges) {
		node a = M.copy(eOrig->source());
		node b = M.copy(eOrig->target());
		M.newEdge(a, b);
	}
	return (isAcyclic(M));
}

	static edge crossedEdge(adjEntry adj)
	{
		edge e = adj->theEdge();

		adj = adj->cyclicSucc();
		while (adj->theEdge() == e)
			adj = adj->cyclicSucc();

		return adj->theEdge();
	}

// computes the leftist canonical order. Requires that G is simple, triconnected and embedded.
// adj_v1n is the adjEntry at v_1 looking towards v_n, the outerface is choosen such that v_2 is the cyclic pred
// of v_n. the result is saved in result, a list of list of nodes, first set is v_1, v_2, last one is v_n.
bool LeftistOrdering::call(const Graph& G, adjEntry adj_v1n, List<List<node> >& result)
{
    // init the is marked array for all adj entries
    m_marked.init(G, false);

    // v1 -> v_n edge
    adjEntry adj_v12 = adj_v1n->cyclicPred();

    // the node v_n
    node v_n = adj_v1n->twinNode();

    // init all the node related arrays
    m_cutFaces.init(G, 0);
    m_cutEdges.init(G, 0);
    m_cutFaces[v_n] = 1;

    // mark v_1 -> v_n
    m_marked[adj_v12] = true;
    m_marked[adj_v12->twin()] = true;

    // initial candidate for the belt
    Candidate v12_candidate;
    v12_candidate.chain.pushBack(adj_v12->twin()); // edge 2->1
    v12_candidate.chain.pushBack(adj_v12);         // edge 1->2
    v12_candidate.chain.pushBack(adj_v12->twin()); // edge 2->1
    v12_candidate.stopper = nullptr;

    // init the belt
    m_belt.pushBack(v12_candidate);

    // init the candidate variable
    // we us an iterator here to keep things simple
    m_currCandidateIt = m_belt.begin();

    // while the belt contains some candidates
    while (!m_belt.empty())
    {
        // the next partition
        List<node> P_k;

        // get the next leftmost feasible candidate
        if (!leftmostFeasibleCandidate(P_k))
            return false;

        // update the belt
        updateBelt();

        // save the result.
        result.pushBack(P_k);
    }
    // thats it we are done
    return true;
}

	double compare(const adjEntry adjEntry1, const adjEntry adjEntry2) const {
		edge e = adjEntry1->theEdge();
		edge f = adjEntry2->theEdge();

		int result = 0;

		if(m_edgeCosts != nullptr) {
			result = (*m_edgeCosts)[e] - (*m_edgeCosts)[f];
		}

		return result;
	}

// creates a virtual vertex of vertex father and embeds it as
// root in the biconnected child component containing of one edge
void BoyerMyrvoldInit::createVirtualVertex(const adjEntry father)
{
	// check that adjEntry is valid
	OGDF_ASSERT(father != nullptr);

	// create new virtual Vertex and copy properties from non-virtual node
	const node virt = m_g.newNode();
	m_realVertex[virt] = father->theNode();
	m_dfi[virt] = -m_dfi[father->twinNode()];
	m_nodeFromDFI[m_dfi[virt]] = virt;

	// set links for traversal of bicomps
	m_link[CW][virt] = father->twin();
	m_link[CCW][virt] = father->twin();

	// move edge to new virtual Vertex
	edge e = father->theEdge();
	if (e->source() == father->theNode()) {
		// e is outgoing edge
		m_g.moveSource(e,virt);
	} else {
		// e is ingoing edge
		m_g.moveTarget(e,virt);
	}
}

void PlanarSPQRTree::setPosInEmbedding(
	NodeArray<SListPure<adjEntry> > &adjEdges,
	NodeArray<node> &currentCopy,
	NodeArray<adjEntry> &lastAdj,
	SListPure<node> &current,
	const Skeleton &S,
	adjEntry adj)
{
	node vT = S.treeNode();

	adjEdges[vT].pushBack(adj);

	node vCopy = adj->theNode();
	node vOrig = S.original(vCopy);

	if(currentCopy[vT] == nullptr) {
		currentCopy[vT] = vCopy;
		current.pushBack(vT);

		for (adjEntry adjVirt : vCopy->adjEdges) {
			edge eCopy = S.twinEdge(adjVirt->theEdge());
			if (eCopy == nullptr) continue;
			if (adjVirt == adj) {
				lastAdj[vT] = adj;
				continue;
			}

			const Skeleton &STwin = skeleton(S.twinTreeNode(adjVirt->theEdge()));

			adjEntry adjCopy = (STwin.original(eCopy->source()) == vOrig) ?
				eCopy->adjSource() : eCopy->adjTarget();

			setPosInEmbedding(adjEdges,currentCopy,lastAdj,current,
				STwin, adjCopy);
		}

	} else if (lastAdj[vT] != nullptr && lastAdj[vT] != adj) {
		adjEntry adjVirt = lastAdj[vT];
		edge eCopy = S.twinEdge(adjVirt->theEdge());

		const Skeleton &STwin = skeleton(S.twinTreeNode(adjVirt->theEdge()));

		adjEntry adjCopy = (STwin.original(eCopy->source()) == vOrig) ?
			eCopy->adjSource() : eCopy->adjTarget();

		setPosInEmbedding(adjEdges,currentCopy,lastAdj,current,
			STwin, adjCopy);

		lastAdj[vT] = nullptr;
	}

}

node CombinatorialEmbedding::splitNode(adjEntry adjStartLeft, adjEntry adjStartRight)
{
	face fL = leftFace(adjStartLeft);
	face fR = leftFace(adjStartRight);

	node u = m_pGraph->splitNode(adjStartLeft,adjStartRight);

	adjEntry adj = adjStartLeft->cyclicPred();

	m_rightFace[adj] = fL;
	++fL->m_size;
	m_rightFace[adj->twin()] = fR;
	++fR->m_size;

	OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());

	return u;
}

	void FixEdgeInserterUMLCore::insertEdgesIntoDual(const CombinatorialEmbedding &E, adjEntry adjSrc)
	{
		face f = E.rightFace(adjSrc);
		node vRight = m_nodeOf[f];

		adjEntry adj1 = f->firstAdj(), adj = adj1;
		do {
			node vLeft = m_nodeOf[E.leftFace(adj)];

			edge eLR = m_dual.newEdge(vLeft,vRight);
			m_primalAdj[eLR] = adj;

			edge eRL = m_dual.newEdge(vRight,vLeft);
			m_primalAdj[eRL] = adj->twin();

			if(m_pr.typeOf(adj->theEdge()) == Graph::generalization)
				m_primalIsGen[eLR] = m_primalIsGen[eRL] = true;
		}
		while((adj = adj->faceCycleSucc()) != adj1);

		// the other face adjacent to *itEdge ...
		f = E.rightFace(adjSrc->twin());
		vRight = m_nodeOf[f];

		adj1 = f->firstAdj();
		adj = adj1;
		do {
			node vLeft = m_nodeOf[E.leftFace(adj)];

			edge eLR = m_dual.newEdge(vLeft,vRight);
			m_primalAdj[eLR] = adj;

			edge eRL = m_dual.newEdge(vRight,vLeft);
			m_primalAdj[eRL] = adj->twin();

			if(m_pr.typeOf(adj->theEdge()) == Graph::generalization)
				m_primalIsGen[eLR] = m_primalIsGen[eRL] = true;
		}
		while((adj = adj->faceCycleSucc()) != adj1);
	}

void GridLayoutPlanRepModule::doCall(
	const Graph &G,
	adjEntry adjExternal,
	GridLayout &gridLayout,
	IPoint &boundingBox,
	bool fixEmbedding)
{
	// create temporary graph copy and grid layout
	PlanRep PG(G);
	PG.initCC(0); // currently only for a single component!
	GridLayout glPG(PG);

	// determine adjacency entry on external face of PG (if required)
	if(adjExternal != nullptr) {
		edge eG  = adjExternal->theEdge();
		edge ePG = PG.copy(eG);
		adjExternal = (adjExternal == eG->adjSource()) ? ePG->adjSource() : ePG->adjTarget();
	}

	// call algorithm for copy
	doCall(PG,adjExternal,glPG,boundingBox,fixEmbedding);

	// extract layout for original graph
	for(node v : G.nodes) {
		node vPG = PG.copy(v);
		gridLayout.x(v) = glPG.x(vPG);
		gridLayout.y(v) = glPG.y(vPG);
	}

	for(edge e : G.edges) {
		IPolyline &ipl = gridLayout.bends(e);
		ipl.clear();

		for(edge ec : PG.chain(e))
			ipl.conc(glPG.bends(ec));
	}
}

void print_arc(adjEntry a)
{
  printf(" %d->%d", a->theNode()->index(), a->twinNode()->index());
}

bool FUPSSimple::constructMergeGraph(GraphCopy &M, adjEntry adj_orig, const List<edge> &orig_edges)
{
	CombinatorialEmbedding Beta(M);

	//set ext. face of Beta
	adjEntry ext_adj = M.copy(adj_orig->theEdge())->adjSource();
	Beta.setExternalFace(Beta.rightFace(ext_adj));

	//*************************** debug ********************************
	/*
	cout << endl << "FUPS : " << endl;
	for(face ff : Beta.faces) {
		cout << "face " << ff->index() << ": ";
		adjEntry adjNext = ff->firstAdj();
		do {
			cout << adjNext->theEdge() << "; ";
			adjNext = adjNext->faceCycleSucc();
		} while(adjNext != ff->firstAdj());
		cout << endl;
	}
	if (Beta.externalFace() != 0)
		cout << "ext. face of the graph is: " << Beta.externalFace()->index() << endl;
	else
		cout << "no ext. face set." << endl;
	*/

	FaceSinkGraph fsg(Beta, M.copy(adj_orig->theNode()));
	SList<node> aug_nodes;
	SList<edge> aug_edges;
	SList<face> fList;
	fsg.possibleExternalFaces(fList); // use this method to call the methode checkForest()
	node v_ext = fsg.faceNodeOf(Beta.externalFace());

	OGDF_ASSERT(v_ext != 0);

	fsg.stAugmentation(v_ext, M, aug_nodes, aug_edges);

	/*
	//------------------------------------debug
	GraphAttributes AG(M, GraphAttributes::nodeGraphics|
						GraphAttributes::edgeGraphics|
						GraphAttributes::nodeColor|
						GraphAttributes::edgeColor|
						GraphAttributes::nodeLabel|
						GraphAttributes::edgeLabel
						);
	// label the nodes with their index
	for(node v : AG.constGraph().nodes) {
		AG.label(v) = to_string(v->index());
	}
	AG.writeGML("c:/temp/MergeFUPS.gml");
	*/


	OGDF_ASSERT(isStGraph(M));

	//add the deleted edges
	for(edge eOrig : orig_edges) {
		node a = M.copy(eOrig->source());
		node b = M.copy(eOrig->target());
		M.newEdge(a, b);
	}
	return (isAcyclic(M));
}

void PlanarStraightLayout::doCall(
	const Graph &G,
	adjEntry adjExternal,
	GridLayout &gridLayout,
	IPoint &boundingBox,
	bool fixEmbedding)
{
	// require to have a planar graph without multi-edges and self-loops;
	// planarity is checked below
	OGDF_ASSERT(isSimple(G) && isLoopFree(G));

	// handle special case of graphs with less than 3 nodes
	if(G.numberOfNodes() < 3)
	{
		node v1, v2;
		switch(G.numberOfNodes())
		{
		case 0:
			boundingBox = IPoint(0,0);
			return;

		case 1:
			v1 = G.firstNode();
			gridLayout.x(v1) = gridLayout.y(v1) = 0;
			boundingBox = IPoint(0,0);
			return;

		case 2:
			v1 = G.firstNode();
			v2 = G.lastNode ();
			gridLayout.x(v1) = gridLayout.y(v1) = gridLayout.y(v2) = 0;
			gridLayout.x(v2) = 1;
			boundingBox = IPoint(1,0);
			return;
		}
	}

	// we make a copy of G since we use planar biconnected augmentation
	GraphCopySimple GC(G);

	if(fixEmbedding) {
		// determine adjacency entry on external face of GC (if required)
		if(adjExternal != 0) {
			edge eG  = adjExternal->theEdge();
			edge eGC = GC.copy(eG);
			adjExternal = (adjExternal == eG->adjSource()) ? eGC->adjSource() : eGC->adjTarget();
		}

		PlanarAugmentationFix augmenter;
		augmenter.call(GC);

	} else {
		adjExternal = 0;

		// augment graph planar biconnected
		m_augmenter.get().call(GC);

		// embed augmented graph
		m_embedder.get().call(GC,adjExternal);
	}

	// compute shelling order with shelling order module
	m_computeOrder.get().baseRatio(m_baseRatio);

	ShellingOrder order;
	m_computeOrder.get().callLeftmost(GC,order,adjExternal);

	// compute grid coordinates for GC
	NodeArray<int> x(GC), y(GC);
	computeCoordinates(GC,order,x,y);

	boundingBox.m_x = x[order(1,order.len(1))];
	boundingBox.m_y = 0;
	node v;
	forall_nodes(v,GC)
		if(y[v] > boundingBox.m_y) boundingBox.m_y = y[v];

	// copy coordinates from GC to G
	forall_nodes(v,G) {
		node vCopy = GC.copy(v);
		gridLayout.x(v) = x[vCopy];
		gridLayout.y(v) = y[vCopy];
	}

void SchnyderLayout::schnyderEmbedding(
	GraphCopy& GC,
	GridLayout &gridLayout,
	adjEntry adjExternal)
{
	NodeArray<int> &xcoord = gridLayout.x();
	NodeArray<int> &ycoord = gridLayout.y();

	node v;
	List<node> L;						// (un)contraction order
	GraphCopy T = GraphCopy(GC);		// the realizer tree (reverse direction of edges!!!)
	EdgeArray<int> rValues(T);			// the realizer values

	// choose outer face a,b,c
	adjEntry adja;
	if (adjExternal != 0) {
		edge eG  = adjExternal->theEdge();
		edge eGC = GC.copy(eG);
		adja = (adjExternal == eG->adjSource()) ? eGC->adjSource() : eGC->adjTarget();
	}
	else {
		adja = GC.firstEdge()->adjSource();
	}
	adjEntry adjb = adja->faceCyclePred();
	adjEntry adjc = adjb->faceCyclePred();

	node a = adja->theNode();
	node b = adjb->theNode();
	node c = adjc->theNode();

	node a_in_T = T.copy(GC.original(a));
	node b_in_T = T.copy(GC.original(b));
	node c_in_T = T.copy(GC.original(c));

	contract(GC, a, b, c, L);

	realizer(GC, L, a, b, c, rValues, T);

	NodeArray<int>  t1(T);
	NodeArray<int>  t2(T);
	NodeArray<int>  val(T, 1);

	NodeArray<int>  P1(T);
	NodeArray<int>  P3(T);
	NodeArray<int>  v1(T);
	NodeArray<int>  v2(T);

	subtreeSizes(rValues, 1, a_in_T, t1);
	subtreeSizes(rValues, 2, b_in_T, t2);

	prefixSum(rValues, 1, a_in_T, val, P1);
	prefixSum(rValues, 3, c_in_T, val, P3);
	// now Pi  =  depth of all nodes in Tree T(i) (depth[root] = 1)

	prefixSum(rValues, 2, b_in_T, t1, v1);
	// special treatment for a
	v1[a_in_T] = t1[a_in_T];

	/*
	 * v1[v] now is the sum of the
	 * "count of nodes in t1" minus the "subtree size for node x"
	 * for every node x on a path from b to v in t2
	 */

	prefixSum(rValues, 3, c_in_T, t1, val);
	// special treatment for a
	val[a_in_T] = t1[a_in_T];

	/*
	 * val[v] now is the sum of the
	 * "count of nodes in t1" minus the "subtree size for node x"
	 * for every node x on a path from c to v in t3
	 */

	// r1[v]=v1[v]+val[v]-t1[v] is the number of nodes in region 1 from v
	forall_nodes(v, T) {
		// calc v1'
		v1[v] += val[v] - t1[v] - P3[v];
	}

int EdgeComparerSimple::compare(const adjEntry &e1, const adjEntry &e2) const
{
	// set true if the algorithm should consider the bend-points
	bool useBends = true;

	double xP1, xP2, yP1, yP2;

	DPolyline poly = m_AG->bends(e1->theEdge());
	ListIterator<DPoint> it;
	DPoint pE1, pE2;

	if ((useBends) && (poly.size() > 2)){
		it = poly.begin();

		while (it.valid()){
			it++;
		}

		if (e1->theEdge()->source() == basis){
			it = poly.begin();
			it++;
		}
		else{
			it = poly.rbegin();
			it--;
		}
		pE1 = *it;
	}
	else{
		pE1.m_x = m_AG->x((e1->twinNode()));
		pE1.m_y = m_AG->y((e1->twinNode()));
	}

	poly = m_AG->bends(e2->theEdge());
	if ((useBends) && (poly.size() > 2)){
		it = poly.begin();

		while (it.valid()){
			it++;
		}

		if (e2->theEdge()->source() == basis){
			it = poly.begin();
			it++;
		}
		else{
			it = poly.rbegin();
			it--;
		}
		pE2 = *it;
	}
	else{
		pE2.m_x = m_AG->x((e2->twinNode()));
		pE2.m_y = m_AG->y((e2->twinNode()));
	}


	xP1 = -(m_AG->x(basis)) + (pE1.m_x);
	yP1 = -(m_AG->y(basis)) + (pE1.m_y);

	xP2 = -(m_AG->x(basis)) + (pE2.m_x);
	yP2 = -(m_AG->y(basis)) + (pE2.m_y);

	if ((yP1 >= 0) && (yP2 < 0))
		return 1;
	if ((yP1 < 0) && (yP2 >= 0))
		return -1;
	if ((yP1 >= 0) && (yP2 >= 0)){

		if ((xP1 >= 0) && (xP2 < 0))
			return -1;
		if ((xP1 < 0) && (xP2 >= 0))
			return 1;

		xP1 = xP1 / (sqrt(xP1*xP1 + yP1*yP1));
		xP2 = xP2 / (sqrt(xP2*xP2 + yP2*yP2));
		if (xP1 > xP2)
			return -1;
		else
			return 1;
	}
	if ((yP1 < 0) && (yP2 < 0)){

		if ((xP1 >= 0) && (xP2 < 0))
			return 1;
		if ((xP1 < 0) && (xP2 >= 0))
			return -1;

		xP1 = xP1 / (sqrt(xP1*xP1 + yP1*yP1));
		xP2 = xP2 / (sqrt(xP2*xP2 + yP2*yP2));
		if (xP1 > xP2)
			return 1;
		else
			return -1;
	}

	return 0;
}

void FPPLayout::computeOrder(
	const GraphCopy &G,
	NodeArray<int> &num,
	NodeArray<adjEntry> &e_wp,
	NodeArray<adjEntry> &e_wq,
	adjEntry e_12,
	adjEntry e_2n,
	adjEntry e_n1)
{
	NodeArray<int> num_diag(G, 0);							// number of chords
	// link[v] = Iterator in possible, that points to v (if diag[v] = 0 and outer[v] = TRUE)
	NodeArray<ListIterator<node> > link(G, 0);
	// outer[v] = TRUE <=> v is a node of the actual outer face
	NodeArray<bool> outer(G, false);
	// List of all nodes v with outer[v] = TRUE and diag[v] = 0
	List<node> possible;

	// nodes of the outer triangle (v_1,v_2,v_n)
	node v_1 = e_12->theNode();
	node v_2 = e_2n->theNode();
	node v_n = e_n1->theNode();
	node v_k, wp, wq, u;
	adjEntry e, e2;
	int k;

	// initialization: beginn with outer face (v_1,v_2,v_n)
	// v_n is the only possible node
	num[v_1] = 1;
	num[v_2] = 2;

	outer[v_1] = true;
	outer[v_2] = true;
	outer[v_n] = true;

	link[v_n] = possible.pushBack(v_n);

	e_wq[v_1] = e_n1->twin();
	e_wp[v_2] = e_2n;

	e_wq[v_n] = e_2n->twin();
	e_wp[v_n] = e_n1;

	// select next v_k and delete it
	for (k = G.numberOfNodes(); k >= 3; k--) {
		v_k = possible.popFrontRet();	// select arbitrary node from possible as v_k

		num[v_k] = k;

		// predecessor wp and successor wq from vk in C_k (actual outer face)
		wq = (e_wq [v_k])->twinNode();
		wp = (e_wp [v_k])->twinNode();

		// v_k not in C_k-1 anymore
		outer[v_k] = false;

		// shortfall of a chord?
		if (e_wq[wp]->cyclicSucc()->twinNode() == wq) {   // wp, wq is the only successor of vk in G_k
			// wp, wq loose a chord
			if (--num_diag[wp] == 0) {
				link[wp] = possible.pushBack(wp);
			}
			if (--num_diag[wq] == 0) {
				link[wq] = possible.pushBack(wq);
			}
		}

		// update or initialize e_wq, e_wp
		e_wq[wp] = e_wq[wp]->cyclicSucc();

		e_wp[wq] = e_wp[wq]->cyclicPred();
		e = e_wq[wp];
		for (u = e->twinNode(); u != wq; u = e->twinNode()) {
			outer[u] = true;
			e_wp[u] = e->twin();
			e = e_wq[u] = e_wp[u]->cyclicSucc()->cyclicSucc();

			// search for new chords
			for (e2 = e_wp[u]->cyclicPred(); e2 != e_wq[u]; e2 = e2->cyclicPred()) {
				node w = e2->twinNode();
				if (outer[w] == true) {
					++num_diag[u];
					if (w != v_1 && w != v_2)
						if (++num_diag[w] == 1) possible.del(link[w]);
				}
			}

			if (num_diag[u] == 0) {
				link[u] = possible.pushBack(u);
			}
		}
	}
}

void FPPLayout::doCall(
	const Graph &G,
	adjEntry adjExternal,
	GridLayout &gridLayout,
	IPoint &boundingBox,
	bool fixEmbedding)
{
	// check for double edges & self loops
	OGDF_ASSERT(isSimple(G));

	// handle special case of graphs with less than 3 nodes
	if (G.numberOfNodes() < 3) {
		node v1, v2;
		switch (G.numberOfNodes()) {
		case 0:
			boundingBox = IPoint(0, 0);
			return;

		case 1:
			v1 = G.firstNode();
			gridLayout.x(v1) = gridLayout.y(v1) = 0;
			boundingBox = IPoint(0, 0);
			return;

		case 2:
			v1 = G.firstNode();
			v2 = G.lastNode();
			gridLayout.x(v1) = gridLayout.y(v1) = gridLayout.y(v2) = 0;
			gridLayout.x(v2) = 1;
			boundingBox = IPoint(1, 0);
			return;
		}
	}

	// make a copy for triangulation
	GraphCopy GC(G);

	// embed
	if (!fixEmbedding) {
		if (planarEmbed(GC) == false) {
			OGDF_THROW_PARAM(PreconditionViolatedException, pvcPlanar);
		}
	}

	triangulate(GC);

	// get edges for outer face (triangle)
	adjEntry e_12;
	if (adjExternal != 0) {
		edge eG  = adjExternal->theEdge();
		edge eGC = GC.copy(eG);
		e_12 = (adjExternal == eG->adjSource()) ? eGC->adjSource() : eGC->adjTarget();
	}
	else {
		e_12 = GC.firstEdge()->adjSource();
	}
	adjEntry e_2n = e_12->faceCycleSucc();

	NodeArray<int>  num(GC);

	NodeArray<adjEntry> e_wp(GC);					// List of predecessors on circle C_k
	NodeArray<adjEntry> e_wq(GC);					// List of successors on circle  C_k

	computeOrder(GC, num , e_wp, e_wq, e_12, e_2n, e_2n->faceCycleSucc());
	computeCoordinates(GC, boundingBox, gridLayout, num, e_wp, e_wq);
}