Hannah Obersteller
email: hobersteller@datenschutzzentrum.de

Anonymous ePetitions -Another Step towards eDemocracy

Keywords: Privacy, Privacy-ABCs, eDemocracy, ePetitions, Anonymity

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1

Introduction 1A petition is a democratic instrument that allowsin generalthe members of a country, a state or other kinds of community to introduce their concerns to the political decision-makers and thereby influence the political dialogue. The petition offers the possibility to raise an issue and obliges the democratically elected representatives to address this issue. E.g., the German constitution (Grundgesetz; abbr.: GG) guarantees everyone to petition the public authorities (Art. 17 GG). Art. 45c GG determines that a committee of petitions shall be established. This text, however, will focus on petitions to parliaments.

In the last few years, citizens have been provided an increasing number of ways to get into contact with public administrations. In the context of the so-called "egovernment movement" many administrative issues now can be performed by sending e-mails or using online services. The current German and European legislation allows for the possibility to file petitions online. Advantages of information and communication technologies, as e.g. being independent from time and location (cf. [START_REF] Märker | E-Participation[END_REF], pp. 357, 358), support these methods of e-participation. This paper focuses on the advancement and improvement of the existing systems with regard to the protection of the citizens' right to privacy.

For instance, in 2005 the German federal Parliament (Bundestag) introduced the possibility to file petitions online. At the same time, a new form of petitions was introduced: public petitions. A public petition is published on the Internet, i.e. on the website of the Bundestag, and can be signed by other people during four weeks. The Directive on public petitions which concretizes the Rules of Procedure of the Bundestag (RoP BT) determines that the petitioner has to indicate his name, permanent address and e-mail address. If the petition is meant to be a public petition, the name and contact address of the petitioner will be published with the petition text. (According to the "Help" section of the Bundestag's website, only the name of the petitioner is published [START_REF]Deutscher Bundestag: Petition zur Veröffentlichung einreichen[END_REF].)

While already the fact that a petitioner has to identify herself by revealing her name and full address to the petition committee, as petition recipient, is to be considered as critical, the publication online is an even stronger intrusion in the petitioner's privacy. The employment of Privacy-enhancing Attribute-based Credentials could be a solution. This technology allows petitioners (and signees) to stay completely anonymous while at the same time it is guaranteed that they are legitimized and do not sign a petition several times when only one signature per person is allowed. Note that current systems do not prevent multiple signing if someone has more than one e-mail address.

The objective of this paper is to discuss how far it is possible to introduce a system which allows submitting a petition not only online but at the same time anonymously, i.e. without disclosing one's name and address to the respective petition committees. The reasoning is based on European legislation. In addition, German legislation is analyzed for input on the Member State level. Furthermore, it is debated how far staying anonymous is possible when submitting a simple petition or a petition that is to be signed by other citizens and, finally, if signees can stay anonymous in the latter case, too.

The text is organized as follows: First, key terms are defined in Section 2. Section 3 provides an overview of the current legal framework concerning anonymous use of online services and petitions on European and German level. Obstacles to overcome are discussed in Section 4. Finally, it is concluded that anonymous ePetitions would support eDemocracy.

Definitions

Petitions and "ePetitions"

Traditionally, a petition is submitted as a document, written on paper, signed in manuscript by the petitioner(s). Nowadays, public authorities increasingly allow the submission via online form. The general process of a petition stays the same and is as follows:

1. A citizen (the petitioner) formulates her concern in writing. Often a (online) form is provided. Inter alia she has to provide her full name and address, in order to allow the public authority to identify the petitioner and contact her by post.

2. The public authority that receives the petition is obliged to examine the admissibility of the petition (compliance with the respective procedural requirements, e.g. competence of the public authority on the petition subject). Mostly, parliaments have established petition committees that process the incoming petitions. 3. If the petition is admissible, the petition committee is obliged to decide on the petition. The exact procedure (oral proceedings/summons of the petitioner or just a written decision with or without grounds) depends on the individual case.

But the petition committee is obliged to reply to the petition and to send the petitioner a final reply. There are different possible understandings of the term "electronic petition" (or: "ePetition"): It can be defined as the submission of a petition to the addressee electronically. In this case the only aspect different for ePetitions compared to "traditional" petitions (in writing) is the modernized way of filing. The actual petitions process would not have to change ([3], p. 11). Another definition of "ePetition" could be "a petition that is published on the Internet". It does not necessarily have to be submitted electronically, but the further petitions process would happen online ([3], p. 11). Within this latter case one can make another distinction between a passive and an active way of use. A passive way of use would be that the petition (and eventually the petition notice) is simply made visible online. An active way of use would mean that an electronic petition system is set up, which especially enables people to file, and others to sign the petition online ([3], p. 12).

In the following "ePetition" will be understood as a petition filed (and possibly published) online and "public ePetition" will be understood as a petition filed online and published on the Internet that can be signed by other people (signees) online. This understanding of "public ePetition" corresponds to the definition of "public petition" laid down in the Rules of Procedure of the Bundestag concerning petitions (see 2 (4) RoP BT). On the European level, only (simple) ePetitions exist. Both kinds of ePetitions can be filed by several petitioners together.

Privacy-enhancing Attribute-based Credentials

Privacy-enhancing Attribute-based Credentials (Privacy-ABCs) give the user control over which, and how much personal information she reveals. They allow authentication towards an online service provider without identification. In a Privacy-ABC system the following entities are mandatory: issuer, user and verifier.

The issuer knows and can vouch for attribute values of the user. The issuer issues a Privacy-ABC credential containing those attributes to the user. The user receives the credential. Whenever the user wishes to authenticate, the credential on her device is combined with her individual secret key that only she possesses. The result is called a token. The user now can use this token to provide proof of certain attributes towards a third partynormally a service providerwhich is called the verifier. The verifier offers a certain online service and usually has a presentation policy that determines which information is demanded to access the service. If e.g. the verifier is an information portal of town X that offers the possibility to ask questions on community issues to the inhabitants of town X, the user will only have to prove that she is an inhabitant of town X. Further information that may be contained in the user's credential, like e.g. her name and exact address, she can strip off. If the information stored in the token that the user provides meets the requirements of the verifier's presentation policy, the user is allowed to access the desired service. As a result, the user does not have to reveal more information than absolutely needed to make use of a certain online service. This supports the data minimization principle (see also Section 4.2).

Besides the above mentioned mandatory entities, a Privacy-ABC system can additionally comprise further entities: If full anonymity is not desired, ways for conditional identification can be allowed. This would be done by adding the "inspection feature"." This means, in order to allow the revealing of the user's identity if necessary, an independent "inspection entity" can be employed. The "inspector" is allowed and enabled to identify the user only if predefined conditions are fulfilled. Those "inspection grounds" could, for instance, allow the revealing the identity of a user in case of misuse or infringement of third parties' rights. They have to be made known to the user in advance. Furthermore, it may become necessary to revoke a credential, e.g. if the user's attributes, stored in this credential, have changed. For this purpose, a "revocation authority" can be established. The inspection and revocation processes have been discussed in detail in [START_REF] Bieker | Towards a privacy-preserving inspection process for authentication solutions with conditional identification[END_REF].

In principle, the user can be enabled to act completely anonymously. However, while Privacy-ABCs allow anonymous authentication, the implementation has to be considered in detail as certain circumstances, such as the specific value of revealed attributes, tracking measures (cookies etc.) and IP addresses, may hinder this capability. An illustrative example of how a Privacy-ABC-based petition system which allows complete anonymity could be implemented was already given and discussed in the past in [START_REF] Diaz | Privacy preserving electronic petitions[END_REF].

Anonymity

According to the European Data Protection Directive (Directive 95/46/EC of the European Parliament and of the Council of 24 October 1995 on the protection of individuals with regard to the processing of personal data and on the free movement of such data; respectively its national implementing laws), a data subject is considered as anonymous if she is not or no longer identified or identifiable. "(…) To determine whether a person is identifiable, account should be taken of all the means likely reasonably to be used either by the controller or by any other person to identify the said person (…)." (European Data Protection Directive; Recital 26; omissions by the author; cf. the draft General Data Protection Regulation, Recital 23) "Identification" does not only mean that it is possible to retrieve a data subject's name and/or address, but also identifiability by singling out, linkability and interference ([6], p. 10). The document referenced in [6] also explains in detail different ways of anonymization. In general, identifiability of a single individual depends to a large extent on the distinguishability of this person within a set of individuals. The larger the set of people sharing the same attributes values is, the more unlikely is the identification of an individual. So ideally, an anonymous ePetition system has to avoid storing information that might allow the data controlleror an external attackerto directly iden-tify the users or link the information with other databases and use the retrieved information in connection, in order to identify the users ( [START_REF] Abendroth | ABC4Trust D5.2a Amendment Building Blocks of ABC Technology[END_REF], p.42).

Privacy-ABCs systems provide a possible solution, since the service providerin this case the provider of the ePetition platformdoes not receive more data than absolutely necessary and, consequently, cannot store them. In most cases, e.g., it is sufficient to prove that one is citizen of a certain state (or maybe region) to participate in a certain ePetition. Still, Privacy-ABCs allow to make sure that a citizen signs a petition not more often than once. (See also Section 4.3. For more details on the technical solution please refer to [START_REF] Bcheri | ABC4Trust D5.3 Experiences and Feedback of the Pilots[END_REF], pp. 128 et sqq.)

However, in case of complete anonymity the European Data Protection Directive is not applicable, since it only regulates the handling of identifying data (Recital 26 Dir. EC/95/46; [6], p. 5). From a legal point of view, anonymity is not given if the user is not identified from the outset but still identifiable ([6], p. 6), i.e. her identity can be revealed. In a Privacy-ABC system which enables the inspection feature, the credentials issued to the user are "inspectable". If the inspection grounds are fulfilled, the inspector is (technically) enabled to reveal the user's identity.

Assuming that an ePetition system will not be accepted by the responsible public authorities if identification is absolutely excluded, it would probably be more accurate to speak of "anonymous or pseudonymous" ePetitions when discussing the possibility of employing Privacy-ABCs with or without the inspection feature for this purpose. But since anonymity (in the legal sense) is technically possible, it seems acceptable to focus on this goal. Pseudonymity, however, means that the linkability of a dataset with the original identity of an individual is reduced ([6], p. 20).

Legislation

Since 1992, the right to petition the European Parliament is laid down in the European legal framework. Prior to that, it was recognized by customary law and mentioned in the Rules of Procedure of the European Parliament ([9], p. 344). Today, it is guaranteed by the Charter of Fundamental Rights of the European Union (CFREU), the Treaty in the Functioning of the European Union (TFEU) and in many constitutions of the EU Member States ( [START_REF]EU Network of Independent Experts on Fundamental Rights: Commentary of the Charter of Fundamental Rights of the European Union[END_REF], p. 344, fn. 1385). As mentioned initially, in Germany it is constitutionally guaranteed in Art. 17 GG. The competence of the respective public authorities depends on the subject of the petition. For instance, the Bundestag is not responsible for the educational policy of the German federal State Schleswig-Holstein. If a petitioner files a petition concerning the inadequate curricula of public schools in Schleswig-Holstein, the Bundestag's petition committee will inform the petitioner that her petition was rejected as inadmissible.

Anonymity

If the operator wishes to store identifying data of the user (e.g. the IP address), he needs a legal permission. As the IP address commonly is regarded as personal data ([10], p. 16), the European Data Protection Directive is applicable. This means, data may only be collected for specified, explicit and legitimate purposes. Under the current German legislation there is no general legal permission (or even obligation) for website operators to know or to store identifying personal data of their users. While telecommunication providers in Germany are obliged to collect identifying personal data such as name, permanent address, date of birth etc. from their customers (cf. § 111 Telecommunications Act; abbr.: TKG), this does not apply to website operators. The latter (usually) are not telecommunication providers.

A "telecommunication provider" is a natural or legal person offering telecommunication services. "Telecommunication services" are offers of telecommunications, including transmission line offers to broadcasting networks, usually for a consideration ( § 3 Nr. 18 TKG). "Telecommunications" means the technical process of sending, transmitting and receiving any kind of message in the form of signs, voice, images or sounds by means of telecommunication systems ( § 3 Nr. 16 TKG).

Provided that the operator of an online petition platform does not run an own telecommunication network, he does not meet this definition as he does not offer access to a telecommunication network. To website operators the German Telemediengesetz (Telemedia Act; abbr.: TMG) applies. Both the TKG and the TMG serve to implement European legislation on national German level; i. The TMG itself does not oblige (or allow) the website operator to store user data. The responsibility and liability of website operators depend on his role. A website operator who is just running and maintaining the website, but does not provide own editorial contributions is regarded as host provider (Art. 14 Directive 2000/31/EC of the European Parliament and of the Council of 8 June 2000 on certain legal aspects of information society services, in particular electronic commerce, in the Internal Market; "Directive on electronic commerce"). Concerning the content a petitioner publishes at the petition platform, the Bundestag (as website operator) does not provide own contributions online. A moderator will just delete user content which is not compliant to the terms of use [11]. Hence, the Bundestag is to be treated as a host provider in this regard. In consequence, a right to store the user's personal data for own business purposes because this is necessary to safeguard its legitimate interests (according to § 28 (1) Nr. 2 Federal German Data Protection Act; abbr.: BDSG) cannot be derived, as a host provider is not responsible for user content. Otherwise the legitimate interest could be e.g. evidence purposes or own legal actions in case of legal proceedings against the website operator due to content published by a user [START_REF] Vg Berlin | Datenschutzrechtliche Anordnung im Fall der Speicherung von Beschäftigtendaten. Urteil vom 13[END_REF]. The host provider is just required to make sure that such content is deleted, respectively not accessible anymore ( § 10 TMG).

The website operator of an Internet forum is not required to provide an individual with personal data of one of the users, even if this user has published content which violates the rights of personality of this individual [13]. In turn, the operator has to provide the prosecution authorities with stored personal data in cases of suspicion of serious criminal offences committed by the user. But if no identifying data is stored, the website operator cannot provide the authorities with such data. Currently, there is no German data retention law: In 2010 the German Constitutional Court (Bundesverfassungsgericht) ruled that the German transposition law to the European Directive on retention of personal data (Directive 2006/24/EC of the European Parliament and of the Council of 15 March 2006 on the retention of data generated or processed in connection with the provision of publicly available electronic communications services or of public communications networks and amending Directive 2002/58/EC) was void.

This may be regarded as an unintended gap, since the technical possibility of complete anonymity just was not considered. But de facto there is not even a rule of law which regulates a comparable issue and therefore could be applied by analogy.

Legal Requirements on Petitions

The right to petition grants that the petition recipient examines the petition content. If the petition recipient comes to the conclusion that the petition is not admissible, the right to petition further grants that the petitioner shall be informed about this fact and the reason for the inadmissibility. Reason for this is to allow the petitioner to make a decision on whether she wants to appeal the decision and to allow a judge to review the grounds for lawfulness. Insofar, the right to petition is identical on European and national German level ([14], [START_REF]European Court of Justice: Judgment of the General Court (Sixth Chamber)[END_REF], [START_REF]Judgment of the General Court (Sixth Chamber) of 27[END_REF]). However, as for the national German level, the German constitutional court ruled that the petition committee is not obliged to provide the petitioner (of an admissible petition) with a statement of grounds for its decision. Once a petitioner got a reply for the purpose of notifying the decision on her petition, she has no right to get another reply if she petitions to the same authority for the same reasons again [14].

Under the current legislationleaving aside the subordinate Rules of Procedure, which could be attached autonomously by the respective parliaments or petition committees themselvesit is possible to implement an anonymous ePetition system.

The current Rules of Procedure of both the European Parliament and the Bundestag determine that the petitioner has to identify herself towards the petition committees. Staying anonymous or using a pseudonym towards the petition committee is not allowed.

However, the Rules of Procedure stem from the fact that the treatment of petitions is left to the discretion of the public authorities, as long as the minimum conditions are fulfilled ( [START_REF] Uerpmann-Witzack | Artikel 17 GG[END_REF], marginal 10). The parliaments could change their respective Rules of Procedure and allow anonymous ePetitions as long as compliance with the "minimum conditions" is assured.

European Union. The European legislation allows every citizen of the European

Union and any natural or legal person residing or having its registered office in a Member State to petition the European Parliament alone or jointly with others (Art. 44 CFREU, Art. 227 TFEU). Art. 227 TFEU limits the scope to matters which come within the Union's field of activity and affect the petitioner directly. Petitions will be addressed by the Petition Committee of the European Parliament. According to the Rules of Procedure of the European Parliament (8th parliamentary term, July 2014; abbr.: RoP EP), the Petition Committee is one of the standing committees which are to be set up by the European Parliament (196 RoP EP; Annex VI (XX)).

It is possible to file petitions via an online form (or by post). It is not possible to file a petition as public ePetition, butas Art. 227 TFEU providesto file petitions together with as many other petitioners as desired. The petitioner has to indicate her name, permanent address and nationality. If the petition is published online, the name of the petitioner may be published with the petition's content (215 (9) RoP EP). Basically, all registered petitions will be made public documents and may be published by the European Parliament (215 (9) RoP EP). Nevertheless, the European Parliament has itself undertaken to respect the privacy interests of petitioners to such degree as Rule 215 also stipulates the mandatory non-disclosure of the petitioner's name (Rule 215 (10) RoP EP) or the possible treatment of the petition (the content) as confidential (Rule 215 (11) RoP EP) if the petitioner clearly requests this when filing the petition.

In contrast to the German constitution, neither the CFREU, nor the TFEU states clearly that a petition has to be filed in writing. Still, the RoP EP anticipate that petitions are "written" (c.f. 215 (5) RoP EP: "Petitions must be written in an official language of the European Union."), which of course does not necessarily mean in a traditional -meant as "on paper"way. However, in accordance with the Bundestag, the European Parliament decided to give potential petitioners the ability to file petitions online. But all subsequent communication will happen by post. As this communication could be done electronically as well, there is no absolute hindrance for anonymous ePetitions.

Germany.

As stated in the introduction, on the German federal level the right to petition the Bundestag (and other public authorities) is guaranteed in Art. 17 GG. Art. 45c GG determines that a petition committee is to be appointed by the Bundestag. All powers conferred to the petition committee of the Bundestag are regulated by federal law (Gesetz über die Befugnisse des Petitionsausschusses). All details concerning action taken on petitions are laid down in the petition committee's Rules of Procedure (introduced on the basis of § 110 of the Bundestag's Rules of Procedure; abbr.: GOBT).

Art. 17 GG determines that a petition has to be filed in writing. Traditionally, "in writing" requires a piece of paper with the petition text on it, signed by the petitioner. Accordingly, 4 (1) of the Rules of Procedure of the Bundestag's petition committee (RoP BT) states the written form requirement and adds that it is also observed if the petitioner uses the online form and provides her name and postal address. However, this data is not published on the petition platform; everyone who wants to contribute to the platform has to register.

The name and permanent address data of a public ePetition's so-called main petitioner ("initiator of a public petition") is published online together with the petition text (Nr. 6 of the additional Directive on public ePetitions, [START_REF] Bundestag | Richtlinie für die Behandlung von öffentlichen Petitionen (öP) gem. Ziff 7.1 (4) der Verfahrensgrundsätze[END_REF]). Signees have to register, but can choose to sign the petition under a pseudonym (created by the system). However, this only provides pseudonymity towards other users of the platform.

At the same time, the Bundestag introduced a discussion forum to allow interested parties to discuss a public petition's content. Participation in the forum discussions is only possible under a self-or system-chosen pseudonym [START_REF]Deutscher Bundestag: Petition zur Veröffentlichung einreichen[END_REF]. Petitions including signee lists and contributions to the discussion forum are accessible online throughout three election periods before they are deleted.

It is questionable whether petitions may be filed online in Germany at all. The electronic form could be regarded as constitutionally excluded: According to the jurisdiction of the German constitutional court, it is constitutionally not permissible to conduct parliamentary elections in Germany solely electronically. In a parliamentary democracy the elections of the representatives are the initial and the key element of the chain of democratic legitimacy. Based in this appraisal, the German constitutional court in its grounds mainly refers to the principle of publicity of elections which is derived from Art. 38, in conjunction with Art. 20 ( 1) and ( 2) GG. The court considered the principle as affected, since the usage of electronic voting machines did not allow monitoring the actual voting process (all relevant steps from the voter's individual action to the result) without having expert knowledge [19]. However, the electoral principles only concern parliamentary or general elections and are not transferable to other democratic instruments [20]. Therefore, the petitions process is not affected by the judgement of the German constitutional court initially mentioned and can be conducted electronically (including online). But at the same time, since the electoral principles are not applicable, no rights can be derived from e.g. the principle of secrecy (Art. 38 (1) GG). In other words: The German constitution does not grant the right to be anonymous to petitioners.

Since the Bundestagresp. its petition committee -accepts petitions that are filed via the online form provided at the Bundestag's website, the definition of "in writing" obviously has been adjusted to the modern world. This is not an exception. § 3a of the federal German Administrative Procedure Act stipulates thatif written form is mandatory by lawit may be replaced by electronic form if this is not excluded by (another) legal norm. In context with the eGovernment movement, it is often said that, in general, there are too many written form requirements (e.g. by ISPRAT, [START_REF] Isprat | Stellungnahme zum Referentenentwurf der Bundesregierung eines Gesetzes zur Förderung der elektronischen Verwaltung sowie zur Änderung weiterer Vorschriften (E-Government-Gesetz[END_REF], p. 4).

A decrease of written form requirements to simplify or facilitate the proceedings should not have a negative impact on the reliability or sincerity of the respective declaration of intent in sensitive areas. Therefore, it needs to be considered carefully which written form requirements may be abdicable. For this, it has to be analyzed individually why written form is required first.

According to the traditional understanding, the written form requirement in Art. 17 GG is necessary because it (a) allows to identify the petitioner, (b) allows to answer the petition (send a notice), and (c) assures the seriousness of the petitioner's request ( [START_REF] Klein | Artikel 17 GG[END_REF], marginal 61). Sometimes it is also stated that the (d) anonymous exercise of fundamental rights is "a contradiction in terms" ( [START_REF] Klein | Artikel 17 GG[END_REF], marginal 62).

Here, the written form requirement in Art. 17 GG itself is not to be questioned. But it will be discussed that an online petition platform that employs Privacy-ABCs could fulfill all the requirements set up by the traditional understanding of "in writing" and at the same time protect the petitioner's privacy. A system that applies Privacy-ABCs allows to "identify" the petitioner (criteria (a) from the list above), since the system guarantees that the one who participates is duly accredited. It is not necessary to know the name of the petitioner if it is assured that she exists and has the right to petition. Insofar, as the nationality or permanent residence of the petitioner is of relevance (e.g. any citizen of the European Union and any natural or legal person residing or having its registered office in a Member State can petition the European Parliament, cf. 215 (1) RoP EP), the petitioner will only have to prove the country to the system and will be allowed to file her petition. There is no need for the recipient to learn about the exact address of the petitioner.

A Privacy-ABC system allows contacting the petitioner (criteria (b)). It is possible to implement some sort of chat functionality. The petition committee could communicate its decision online. Another, and probably the preferable, option could be to implement a system which offers a "sharing documents" functionality. In a Privacy-ABC-based communication system it is possible to implement a personal "Restricted Area" for every user ( [START_REF] Bcheri | ABC4Trust D6.3 Evaluation of the School Pilot[END_REF], pp. 19, 33). This allows the petition committee to upload the petition notice (as a document) to the respective petitioner's Restricted Area. Only the petitioner will have access to this area and, consequently, to the document. The system guarantees that only the petitioner can retrieve this document.

Finally, it is not reasonable that an online form can guarantee the seriousness of a petitioner's request less than, say, a post cardwhich, by the way, would fulfill the "in writing" requirements if signed with name (criteria (c) and (d)). Still this online form exists today and therefore apparently is regarded as compliant with the constitution. Occasionally it is even doubted that a petition to the Bundestag filed online enjoys the protection by the constitution because it does not fulfill the constitutionally prescribed form requirements ( [START_REF] Kellner | Die E-Petition zum Bundestag: Ein Danaergeschenk[END_REF], p. 59). But if the public authorities open this door, a discrimination of ePetitions is not acceptable.

Due to the fact that the fundamental right to petition is meant to be exercisable as easily as possible and therefore no other procedural requirements need to be fulfilled ( [START_REF] Krings | Artikel 17 GG[END_REF], marginal 38), it is worth to make it accessible as easy as technically and legally possible. Especially due to the fact that petitions often are regarded as the "ultimate backup" or an "emergency telephone" for the citizens ([3], p. 36), it would be inappropriate to create artificial obstacles. In contrary, all discretion should be used and bureaucratic requirementssuch as a necessarily postal communication with the petitioner, once the petition is filedrethought. Schleswig-Holstein. In the German federal State of Schleswig-Holstein the idea of anonymous ePetitions was proposed by a Member of Parliament, but has not met with broad support by the responsible committees, yet.

The right to petition the Parliament of Schleswig-Holstein (Landtag) is not explicitly laid down in the constitution of Schleswig-Holstein, but arises from the federal constitution, whichof coursealso is applicable at federal state level. The constitution of Schleswig-Holstein (abbr.: LVerf S-H) just states that the State Parliament shall establish a petition committee (Art. 19 (1) LVerf S-H). So the right to petition is not stated, but preconditioned. The procedural rules are similar to those of the Bundestag, in particular they also foresee public ePetitions. Since the minimal conditions arise from the constitution (i.e. the GG), the same approach as on German federal level (see above) should be applied here. An online platform that allows anonymous (public) ePetitions would be legally permissible.

4

Obstacles to Overcome Since a democratic system provides instruments of participation, these instruments should be accessible and attractive to as many citizens as possible. Therefore, potential obstacles have to be removed. Based on the assumption that participating onlinevia an own device, from wherever the user isis convenient, the next step is to discuss if citizens feel comfortable with raising issues and expressing their opinion towards the public authorities, and if they do not, how the offer can be improved. In the following section, major concerns regarding online petition platforms are addressed in order to show that a Privacy-ABC-based system might foster the democratic participation.

Fear of Discrimination by Other People or Public Authorities

In principle, a petition can address any subject. However, most petitions will at least indicate the political opinion of the petitioner (and the signees). The sensitivity of personal data can also result indirectly from the context ( [START_REF] Gola | § 3 BDSG[END_REF], rec. 56a). This may keep people from participating, since they fear negative consequences, or to be attacked for their opinion. The data protection legislation provides stricter requirements concerning the processing of data about political opinions. It is defined as sensitive data (cf. Art. 8 Dir. 95/46/EC). Against this background, the fact that a petitioner has to identify herself with her full name and permanent address towards the public authorities is unsatisfactory not only from a privacy perspective. Especially, it is incomprehensible why the name and permanent address of the initiator of a public ePetition has to become known even to the Internet public. In fact, it would be sufficient to publish the petition text and use a pseudonym here as wellas for the discussion forum, in the case of the Bundestag. On the European level public ePetitions do not exist. But in general, the European Parliament seems to be aware of the problem and thus allows exceptions from its rule to publish petition texts including the petitioners' names.

Anonymity could prevent a (theoretical) possible "there you go again"-reflex of the petition committees in cases of people who petition repeatedly. In general, anonymous petitions allow the most objective and fair decision by the petition committees, as nothing but the content (and maybe the number of signees) is known to them. In fact, very few petitioners are "heavy users". Most of the users of the Bundestag's online platform do not sign more than two petitions ([3], p. 79]. This may also mean: The fewer "troublemakers", the more likely it becomes that they are known by name.

Data Security / System Data Protection

There is a difference between "being on a list that, if any, can be consulted at a town hall"as in case of a traditional referendum, for instance -and "being on a list that is published online". The latter is potentially considerable by the whole online world and -since the information is stored on the public authorities' serversof course, potential target of cyber criminals (data theft). So, even if one does not fear discrimination by the public entities or other users, such security threats have to be considered. As for parliamentary elections, 57 % of the German citizens would prefer not to vote online for doubts about security in general. 37 % explicitly fear misuse of their data [START_REF]im Internet: DIVSI Milieu Study on Trust and Security on the Internet -Condensed Version[END_REF]. At the same time, nearly three out of four Germans (74 %) expect the government and business community to actively ensure online security ( [START_REF]Vertrauen und Sicherheit im Internet: Jeder Zweite möchte online wählen[END_REF], pp. 9-10). And at least nearly 60 % of Germany's population assumes that responsibility for security and data protection on the Internet primarily rests with companies and/or the government, which they expect to create the necessary conditions ([28], p. 12).

Having said this, it is obvious that such data security problems cannot simply be solved by not publishing the names of petitioners (and signees) online. The less data is stored centrally, the better. Already if information is stored that allows reidentification or linkage to other databases, an attacker could use this information in connection with information stored in service or log files of other data controllers to identify a participant. Since with Privacy-ABCs only the information absolutely necessary is revealed to the service provider, the petition committees', resp. the parliaments', servers would have to deal only with a small amount of data (cf. Section 2.3). The data minimization and data avoidance principle addresses this risk. It demands that personal data must be adequate, relevant and not excessive in relation to the purposes for which they are collected and/or further processed (Art. 6 (1) (c) Dir. 95/46/EC). If an anonymous or pseudonymous mode of use is possible, the user shall have this opportunity ([26], marginal 1, 4). A Privacy-ABC-based system could fulfill the requirements arising from the data minimization and data avoidance principle.

Multiple Participation

Another issuenot from a privacy, but general eGovernment perspectiveis to prevent users from participating several times. For instance, the RoP BT determine that if a public ePetition is signed by at least 50,000 people, the petitioner (or several petitioners) will be invited to a personal interview by the petition committee, while normally there is no right to be heard. Even if this may not be considered as a big issue concerning ePetitions, it can be of interest for further use cases such as citizens' initiatives and referendums. In these cases even more rights arise from the achievement of a certain quota. The current ePetition system of the Bundestag, for instance, checks the e-mail address and the IP address of a signee ([3], p. 74). In times of dynamic IP addresses this is clearly not the most reliable method to exclude multiple participations. A Privacy-ABC system, for instance, could be implemented in a way that in case of repeated participation in the petition, only the last signature would be counted (cf. [START_REF] Deibler | ABC4Trust D7.3 Evaluation of the Student Pilot[END_REF], p. 85; [START_REF] Diaz | Privacy preserving electronic petitions[END_REF], p. 213).

Contact the Petitioner

As indicated above, the petition committees are legally obliged to send a note to the petitioner in order to communicate its decision. This issue has already been addressed in Section 3.2 when discussing reasons for the written form requirement on German federal level.

Misuse

Cases of misuse are rare under the current Bundestag system ([3], p. 15]). Considering the fact that at present people could "invent" identities (e.g. by using an assumed name and creating a fake e-mail account), this is in a way remarkable. However, public authorities might fear that anonymity would open up for every conceivable kind of abuse. A public ePetition to the Bundestag is inadmissible, inter alia, if it contains obviously wrong, distorting or offensive expressions. The same holds if the content is obviously impertinent or is based on fundamentally wrong premises. In principle, deletion seems to be sufficient in such cases. But at present, the petition committee could demand criminal prosecution and provide the respective authorities with potentially identifying data, such as the IP address. However, if a Privacy-ABC-based system including the inspection feature (as described in Section 2.2) was employed, the identification of the user would be regulated. Although it is explicitly not intended at this point to vote for an "all identifiable system through the back door", it might be considerable that it is fairer to let the user know the exact conditions under which her identity will be revealed. This would be the case in a Privacy-ABC system with an implemented inspection feature. At the same time, a Privacy-ABC system would provide a strong authentication. Misuse in terms of illegitimate petitions by illegitimate users could be prevented.

Conclusions

It was shown that all guarantees arising from the actual fundamental right to petition can be granted when introducing an anonymous ePetition system which employs Privacy-ABCs. The right to petition is designed as "low barrier" (in terms of "bureaucratic hurdles") democratic instrument and therefore the ideal environment for a completely new and innovative approach. If someone is legitimated to make use of the right to petition, the proof of this legitimization (i.e. being a citizen, living in a specific region etc.) is sufficient. Whether the concern brought up in the petition is legitimate as well is a different matter and does not depend on the person's identity. The benefit of respecting the citizens' fundamental right to privacy is not just a goal in itself. Even if at the moment most people in Europe live in countries that respect their citizens' rights, unfortunately it cannot be granted that it will stay this way.

In the recent past, the European Community has seen political developments in some Member States which indicate that the guarantees of freedom and expression are not as perfectly natural as one may wish for. They need to be watched and defended. Democracy does not work if no one participates due to fear of consequences. Instruments like the petition are a comparatively easy way to report wrongdoing. They deserve reasonable assistance and support from the democratic forces that can be offered.

  e. the Directive 2002/58/EC of the European Parliament and of the Council of 12 July 2002 concerning the processing of personal data and the protection of privacy in the electronic communications sector (e-Privacy Directive) amended by the Directive 2009/136/EC of the European Parliament and the Council of 25 November 2009.

The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under Grant Agreement no.

for the project Attribute-based Credentials for Trust (ABC4Trust).


E Arnaud
email: eric.arnaud@xlim.fri.

C Menudier

J Fouany

T Monediere

M Thevenot

E Arnaud;

X-band Compact Dual Circularly Polarized Isoflux Antenna for nanosatellite applications

Keywords: Nanosatellite application, dual circular polarization, compact choke horn, patch antenna, isoflux radiation pattern

This paper presents an original solution to design a compact dual circularly polarized isoflux antenna (DCPIA) for nanosatellite applications. This kind of antenna has been previously designed in our laboratory, for a single circular polarization. This antenna is composed of a dual circularly polarized feed and a choke horn antenna. This feed is a crossshaped slot in the ground plane which provides coupling between a patch and a ring microstrip line with two ports. It is located at the centre of a choke horn antenna. The simulated antenna presents an axial ratio (AR) lower than 3 dB and a realized gain (RG) close to 0 dB over a 400 MHz bandwidth (8.0-8.4GHz) at the limit of coverage (LOC), i.e. 65° whatever the azimuth angle (φ) and the port. A 20 dB matching for each port and 13 dB isolation characteristics between the two ports have been achieved on this bandwidth. It has been realized and successfully measured.

INTRODUCTION

The requests in high data rate for future nanosatellite missions are incompatible with a telemetry application in VHF or S bands contrary to the X-band. The future antennas will have to present both isoflux radiation pattern and circular polarization (CP). Unfortunately, these two characteristics are often discordant. Several solutions have been previously designed by our laboratory. A trade-off between isoflux pattern quality and antenna size was made in [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF]- [START_REF] Fouany | Circularly polarized isoflux compact X band antenna for nano-satellites applications[END_REF]. Whatever the design, the circular polarization was limited to a single polarization. The main goal of this study is to design a dual circularly polarized isoflux antenna for nanosatellite applications. The simultaneous use of this dual circular polarization will increase the data rate. This antenna will be positioned above a 3U nanosatellite platform (100 x 100 x 300 mm 3 ). Table I presents the antenna performances targets. They are set as objectives but not as definitive specifications. Usually, the choke horn antenna is a good way to perform an isoflux radiation pattern [START_REF] Geyer | Runder Hornstrahler mit ringformigen Sperrtopfen zur gleichzeitigen Ubertragung zweier polarisationsentkoppelter Wellen[END_REF]- [START_REF] Brachat | Sectoral pattern synthesis with primary feeds[END_REF]. Without considering their dimensions, a dual circularly polarization and a good isolation between ports are ordinarily obtained using a septum and an orthomode transducer [START_REF] Davis | A new type of circularly polarized antenna element[END_REF]- [START_REF] Cano | Full band waveguide turnstile junction orthomode transducer with phase matched outputs[END_REF]. Unfortunately, their physical size is not compliant with a nanosatellite application.

Planar solutions such as an array of patches [START_REF] Maldonadoa | Design of concentric ring antenna array for a reconfigurable isoflux pattern[END_REF]- [START_REF] Roy | Handheld Reader Antenna at 5.8 GHz[END_REF] are interesting but they suffer from important dimensions and they require a complex feeding network. The proposed original solution is the association between a patch, used as feed, and a choke horn antenna which is based on [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF]. The first one provides the dual circular polarization while the latter allows realizing the isoflux radiation pattern.

Several authors have already conceived dual circularly polarized with patch antennas. Some of them [START_REF] Boyon | A Novel Single-Feed Circular Microstrip Antenna With Reconfigurable Polarization Capability[END_REF]- [START_REF] Yi-Fan | A Reconfigurable Quadri-Polarization Diversity Aperture-Coupled Patch Antenna[END_REF] used active components such as PIN diodes to create CP. This solution requires one or several DC bias control. It is not able to do the simultaneous polarization. Some other solutions exploit the even and odd modes in a coplanar waveguide transmission line or use a branch line coupler to create CP [START_REF] Narbudowicz | Dual Circularly-Polarized Patch Antenna Using Even and Odd Feed-Line Modes[END_REF]- [START_REF] Bai | Dual-Circularly Polarized Conical-Beam Microstrip Antenna[END_REF]. All these designs limit the antenna miniaturization and the realization easiness. Therefore, in this work the initial feed is based on another solution proposed by Aloni and Zhang [START_REF] Aloni | Analysis of a dual circularly polarized microstrip antenna fed by crossed slots[END_REF]- [START_REF] Zhang | Dual Circularly Polarized Antenna of Compact Structure for RFID Application[END_REF]. It is made of a cross-shaped slot in a ground plane which provides a coupling between a patch and a single ring microstrip line. This paper is organized as follows. Section II is a brief reminder of the compact choke horn antenna. Section III describes the feed optimization (using CST Microwave Studio) to reach the desired antenna characteristics over the entire frequency band. This Section also deals with the association with the compact choke horn. The comparison between retro-simulations and measurements is presented in section IV. Finally, a conclusion is given.

II. Reminder on the compact horn antenna

The already studied design for the choke horn antenna [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF] is reminded in Fig. 1. The radiation patterns present an isoflux shape over the whole frequency band but the maximum gain is obtained for an elevation angle θgm =35° instead of the expected LOC when the mechanical constraints are taken into account. The antenna radiates a mono circular polarization with an AR almost lower than 3 dB at the LOC whatever the azimuth angle (φ). The work in this paper aims to improve this design in order to conceive a dual circularly polarized antenna.

III. Antenna description A)

Description of the structure DCPIA (Fig. 2) is obtained by the addition of a dual circularly polarized patch feed (DCPPF) placed on the choke horn aperture (grayed area). The patch replaces the radiating aperture achieved by the waveguide of the antenna designed in [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF]. Note that the dimensions of this horn have not been changed except the choke height. Indeed, the patch is excited at the center of the antenna and its radiating pattern is transformed by the interaction with the choke, i.e. by reducing this field at the center of the aperture. To provide a null of the aperture field, the radial position and the height of the choke ring are optimized. This optimization depends to the amplitude of the feed aperture field at the center. Since this parameter is similar between the patch and the radiating aperture, the optimization made in [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF] remains correct. On the other hand, the choke height is not uniform (h1 < h2 = 19.85 mm) to have a RG greater than 0 dB at the LOC whatever the frequency. Notice that one of the aforementioned value is still identical to the design in [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF]. The set is inserted into the 3U platform which is simulated as a perfect electric conductor cube but only with a height of 30 mm to reduce the simulation time.

Fig. 2. DCPIA mechanical assembly

The first step towards the goal is to find the best way to realize the feed of DCPIA (Fig. 3).

B) DCPPF design

The feeding part of this antenna is obtained using a cross-shaped slot and a 50 The upper patch which is etched on the top of this same substrate is useful for increasing the isolation bandwidth between both circularly polarized waves. Last substrate (substrate 2) without metallization is identical to the substrate 3 and it is sandwiched between the two other substrates. Firstly, this structure has been optimized in order to obtain the best electromagnetic performances taking into account mechanical constraints. Secondly, the whole antenna has been simulated on the 3U platform. The electromagnetic characteristics are almost identical except the radiation pattern (conventional patch radiation pattern to isoflux radiation pattern). A cylindrical cavity below the patch feed is created to reduce the DCPIA back radiation due to the slot [START_REF] Zhang | A Broadband Single-Feed Circularly Polarized Patch Antenna with Wide Beamwidth[END_REF].

IV. Measurement and simulation validation A)

Realized structure 1) DCPPF realization Fig. 4.b shows the DCPPF realization (back view). Two SMP-M type coaxial connectors are soldered to each input of the 50Ω microstrip line. An adapter SMP-F to SMA-F is connected during measurement. A ring ground plane and via holes are realized to improve the electrical continuity between the 3U platform, the ground plane and the transition SMP/microstrip line. The three printed circuits have been realized in our laboratory with a Circuit Board Plotter and have been assembled by Loctite glue. This last one and the adapters are not taken into account in the simulation. This etching method often involves a substrate thickness decrease where the metallization is removed (in our cases, 1.48 mm instead 1.524 mm for substrates 2 and 3). A retro-simulation was made to take into account all these remarks without optimizing again some parameters such as the slot length.

2)

Manufactured DCPIA Fig. 5 (a-d) shows the manufactured DCPIA. An aluminium thin sheet allows simulating the 3U platform and reducing the interferences of the antenna test range interface.

B)

Comparison between measurements and simulations

1)

Return loss and isolation Fig. 6.a presents the simulated and measured return loss of the two ports. The experimental return loss of each port is higher than the predicted one. This discrepancy is probably due to the SMP connectors soldering. However, this level is below -19 dB over a 400 MHz bandwidth. Fig. 6.b shows the isolation between the ports. A -12 dB isolation is almost obtained between 8.0-8.4 GHz. This isolation is below -20 dB between 8.15-8.35 GHz.

1)

Directivity, realized gain and total efficiency Fig. 7.a shows the comparison between the simulated and the measured directivity and maximum realized gain for the port 1. A satisfactory agreement is observed between these two results. It is the same for the port 2 (Fig. 7.b). A slight discrepancy appears which probably results from a 50 MHz frequency shift of the isolation and the SMP/SMA adapter losses. Fig. 8 shows that the total efficiency of DCPIA is identical to the feed one despite the presence of the horn. Excellent numerical results have been obtained with a total efficiency upper than 90% on the 8.0-8.4 GHz frequency band. The total efficiency measurement would have been close to 90% if no frequency shift appears in the isolation. 2) Radiation pattern and AR Fig. 9 (a-b) show the comparison of the simulated and measured RHCP and LHCP radiation patterns of the port 1 and 2 at the central frequency (8.2 GHz) (RG drawn in the φ = 0° cutplane). An isoflux shape is obtained on the frequency band but the RG is maximum at the θgm= 35° angle instead of 65°. This was the same for the antenna studied in [START_REF] Arnaud | X-band compact choke horn antenna with circular polarization and isoflux pattern for nanosatellite applications[END_REF]. The RG is close to 0 dB whatever the azimuth angle (φ) and the port.

The measured AR radiation patterns (plane φ = 0°) and AR at θ = 65° versus azimuth angle (φ) are close to the simulated ones Fig. 10 (a-b). This characteristic almost meets to the antenna targets. This result would have been almost the same with other cut planes or frequencies. The table II presents a comparison of measured and simulated antenna performances. All the specifications are obtained except the isolation and the LOC.

V. CONCLUSION

This paper completes the previous work on circularly polarized isoflux antenna for nanosatellite applications. The proposed design allows a dual circular polarization of this antenna. A very good agreement between simulation and measurement is obtained even if the -20 dB desired isolation is not satisfied in all bandwidth (2.4 % instead 5%). The result can be improved by increasing the patch substrate thickness and by reducing the dielectric constant as shown in paper [START_REF] Zhang | A Broadband Single-Feed Circularly Polarized Patch Antenna with Wide Beamwidth[END_REF].

Fig. 1 .

 1 Fig. 1. Definition of the compact choke horn antenna

  Ω ring microstrip line (wl = 0.91 mm) respectively etched on the top and bottom of the Duroid 4003C laminate (substrate 1). The circular polarization is obtained by a sequential phase feed of the slot (Lf = 7.4 mm, laf = 0.5 mm). Port1 produces a left circular polarization (LHCP) while Port2 creates a right circular polarization (RHCP). It is necessary that the microstrip line length between each slot branch corresponds to a 90° phase difference, i.e. a quarter of the guided wavelength (Fig. 4.a). The radiating patch part of the antenna is made of two stacked patches. The lowest one is printed on a Duroid 4003C laminate (substrate 3). It includes two circular-shaped notches to improve the LOC AR whatever the azimuth angle (φ).

Fig. 3 .

 3 Fig. 3. Exploded view showing individual layers of the DCPPF.

Fig. 4 .

 4 Fig. 4. Ring microstrip. (a) Sequential phase feed. (b) Realization

Fig. 5 .

 5 Fig. 5. Ring Manufactured DCPIA. (a) Drawing perspective view. (b) Top view photography. (c) Left view photography. (d) Photography of the DCPIA positioned on our antenna test range support

Fig. 7 . 2 Fig. 8 .

 728 Fig. 7. (a) Directivity and Maximum realized gain of port 1. (b) Directivity and Maximum realized gain of port 2

Fig. 9 .

 9 Fig. 9. LHCP and RHCP Radiation patterns (φ = 0° plane). (a) Simulation and measurement of port 1. (b) Simulation and measurement of port 2.

Fig. 10 .

 10 Fig. 10. LHCP AR patterns (φ = 0° plane). (a) port 1. (b) port 2. AR at θ = 65° versus azimuth angle. (c) port 1. (d) port 2

TABLE I : ANTENNA PERFORMANCES TARGET

 I

	Parameter	specification
	Frequency band (GHz)	8.0 -8.4
	Return loss (dB)	< -20
	Isolation between ports (dB)	< -20
	Polarization	RHCP and LHCP
	Limit of coverage (LOC)	65°
	Minimum gain at LOC (dB)	0
	Pattern shape	Isoflux pattern
	Maximum AR(dB) at LOC	3
	Maximum antenna dimensions	90 mm of diameter and 8 mm of height above platform

TABLE II : COMPARISON OF ANTENNA PERFORMANCES

 II

	Parameter		specification
		target	simulation	measurement
	Frequency band (GHz)	8.0 -8.4	8.0 -8.4	8.0 -8.4
	Return loss (dB)	< -20	< -20	< -19
	Isolation between ports (dB)	< -20	< -12	< -11
	Polarization	RHCP and	RHCP and	RHCP and
		LHCP	LHCP	LHCP
	Limit of coverage (LOC)	65°	35°	35°
	Minimum gain at LOC (dB)	0	> 0	> 0
	Pattern shape	Isoflux pattern	Isoflux pattern	Isoflux pattern
	Maximum AR(dB) at LOC	3	< 3	< 3

List of figures and tables


David Auber

Nicolas Bonichon

Paul Dorbec

Claire Pennarun

Rook-drawings of Plane Graphs

We introduce a new type of graph drawing called "rook-drawing". A rook-drawing of a graph G is obtained by placing the n nodes of G on the intersections of a regular grid, such that each row and column of the grid supports exactly one node. This paper focuses on rook-drawings of planar graphs. We first give a linear algorithm to compute a planar straight-line rook-drawing for outerplanar graphs. We then characterize the maximal planar graphs admitting a planar straight-line rook-drawing, which are unique for a given order. Finally, we give a linear time algorithm to compute a polyline planar rook-drawing for plane graphs with at most JGAA, 0(0) 0-0 (0) 1

Introduction

Nowadays, large and dynamic graphs are widely used in the context of Big Data, and their visualization is a classical tool for their analysis. On one hand, when representing dynamic graphs, it is necessary to handle the addition or deletion of nodes or edges easily. On the other hand, when using hierarchical views, the ability to aggregate or de-aggregate sets of nodes is required [START_REF] Abello | ASK-GraphView: A large scale graph visualization system[END_REF][START_REF] Eades | Multilevel visualization of clustered graphs[END_REF]. When doing such operations, it is important to preserve the mental map of the graph [START_REF] Archambault | Mental map preservation helps user orientation in dynamic graphs[END_REF], as well as to compute the changes in the representation efficiently, both in order to guarantee a smooth use.

In the following, we define a new graph drawing style on a grid, that we call rook-drawing. In a rook-drawing, we require that the nodes of the graph lie on the intersections of a (n -1) × (n -1) regular grid, in such a way that each row and column hosts exactly one node. Then, the addition or deletion of a node impacts only the row and column it lies on, without interfering with other nodes or other parts of the drawing. In particular, dealing with aggregated data consists in stretching the grid to create enough room for the new appearing nodes (see Fig. 1). These operations clearly preserve orthogonal ordering, which is the first type of mental map defined in [START_REF] Misue | Layout adjustment and the mental map[END_REF]. Observe that this technique of having exactly one node per row and per column is also used by Kornaropoulos et al. [START_REF] Kornaropoulos | Overloaded orthogonal drawings[END_REF][START_REF] Kornaropoulos | DAGView: an approach for visualizing large graphs[END_REF] and by Angelini et al. [START_REF] Angelini | L-drawings of directed graphs[END_REF], who represented edges with overlapping orthogonal polylines. Here we explore the existence of rook-drawings for planar graphs. The first question that comes to mind is: Does every planar graph admit a planar straightline rook-drawing, i.e. a rook-drawing in which each edge is represented by a segment and no two edges cross? De Fraysseix et al. showed that every planar graph admits a straight-line drawing on an (n -2) × (2n -4) grid [START_REF] De Fraysseix | Small sets supporting Fáry embeddings of planar graphs[END_REF]. Schnyder improved this result by proving the existence of such a drawing on an (n -2) × (n -2)-grid [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF]. But in such drawings, some columns and rows contain several nodes and some others may be empty. Upward-rightward drawings presented by Di Giacomo et al. [START_REF] Di Giacomo | Upward-rightward planar drawings[END_REF] are grid drawings in which all nodes have different y-coordinates, but empty rows and several nodes in a same column are allowed. Contrasting with these results, we show that:

• almost every maximal planar graph admits no planar rook-drawing (see Sect. 3)

• every outerplanar graph admits a planar straight-line rook-drawing computable in linear time (see Sect. 4).

• every planar graph admits a polyline planar rook-drawing, i.e. a planar rook-drawing in which edges are drawn as polylines with bends placed on grid intersections (see Sect. 5). Moreover, this drawing can be computed in linear time, each edge is bent at most once and the total number of bends is at most n -3.

Definitions

A drawing of a graph G is a mapping of the nodes of G to points on the plane and of the edges of G to curves between their endpoints. The drawing is straight-line if the edges are mapped to line segments. It is polyline if the edges are series of line segments. A grid drawing is a drawing in which the nodes are mapped to intersections of a regular grid. In such a drawing, we use positive coordinates (x(u), y(u)) for each node u. A k × l-grid is a grid of width k and height l.

Recall that a rook-drawing of a graph with n vertices is a (n -1) × (n -1)grid drawing, i.e. the functions x and y are bijections from the set of vertices to {1, . . . , n}. For simplicity, throughout this paper, the term "rook-drawing" denotes a straight-line rook-drawing unless otherwise stated.

A planar graph is a graph admitting a planar drawing, i.e. a drawing on the plane in which no two edges cross. Such a drawing can be characterized by the collection of circular permutations of the incident edges around each node of the graph, called an embedding. A planar graph together with an embedding is called a plane graph.

In a plane graph, the edges partition the plane into regions called faces. A rooted plane graph is a plane graph in which one face (called outer face) and one node (called root) lying on this face are distinguished. The nodes lying on the outer face are called outer nodes, all the other nodes are inner nodes. Similarly, outer edges are edges belonging to the outer face, the other edges are called inner edges. An outerplane graph is a rooted plane graph in which every node is on the outer face. A maximal plane graph is a plane graph with maximal number of edges, implying that every face is a triangle if the graph has at least three nodes.

A tree is a rooted plane graph without cycles. In a tree, a node u is a descendant of a node v (or v is an ancestor of u) if v is on the path from the root to u. Moreover, if v is connected to u, we say that v is the parent of u (and u is a child of v). Two nodes are said to be unrelated if one is neither ancestor nor descendant of the other. A leaf of a tree is a node of the tree without descendants. The depth of a tree is the length of the longest path from a leaf to JGAA, 0(0) 0-0 (0) 3 the root in the tree. For a tree T and a node u, the subtree of u, denoted T (u), is the tree induced by u and all of its descendants.

The clockwise preorder of a tree T is a list of the nodes of T in the order of a clockwise depth-first search algorithm on T . The clockwise postorder of a tree T is a list of the nodes of T in the order of their last visit in a clockwise depth-first search algorithm of T . Counterclockwise preorder and postorder are defined similarly.

Existence of a planar rook-drawing

We define the tower plane graph T n of order n ≥ 3 as the plane join graph K 2 + P n-2 (i.e. a complete graph K 2 and a path on n -2 nodes P n-2 together with all the edges joining nodes from K 2 to nodes of P n-2 ) drawn in such a way that the nodes of K 2 are on the outer face (see Fig. 2 for a drawing of T 6 ). The tower plane graph can also be seen as a planar 3-tree where the internal nodes induce a path.

Theorem 1 There exists a unique maximal plane graph on n ≥ 3 nodes admitting a planar rook-drawing, namely the tower plane graph T n .

Proof: Suppose we have a planar rook-drawing of a maximal plane graph G. We prove that G is the tower plane graph T n .

Let a, b, c be the three outer nodes of G. To maintain planarity, the inner nodes are placed at coordinates inside the area defined by the edges (ab), (bc) and (ca). Thus the outer nodes must occupy altogether the four borders of the grid, and one of them has to be placed in a corner. Without loss of generality, assume that a occupies the bottom-left corner.

Consider the positions of the two other outer nodes of G. Suppose one of them is in the top-right corner (without loss of generality, say b). If the third node c is placed below the edge (ab) (see Fig. 3a), then the second column on the left can not contain a node: the coordinates (k, 2) are outside the area delimited by the edges (ab), (bc) and (ca) for all k > 2. The point (2, 2) is covered by (ab) and the point (2, 1) can not contain a node because a is already on the first row. If c is above (ab), then for similar reasons the column left to b can not contain Finally, the inner nodes must be placed on coordinates (i, i) for 2 ≤ i ≤ n -2, i.e. along a diagonal of the grid (see Fig. 3c). Now the positions of the nodes are determined and there is only one way to complete the drawing into a maximal plane graph, forming the graph T n .

Planar rook-drawing for outerplane graphs

In this section, we prove the following theorem:

Theorem 2 Every outerplane graph admits a planar rook-drawing. This drawing can be computed in linear time.

To prove Theorem 2, we use a partition of the edges of an outerplane graph introduced in [5]: Theorem 3 (Bonichon, Gavoille and Hanusse [START_REF] Bonichon | Canonical decomposition of outerplanar maps and application to enumeration, coding, and generation[END_REF]) Let G be an outerplane graph rooted in r. There exists a unique partition of the edges of G into two sets T and S such that: JGAA, 0(0) 0-0 (0) 5 • T is a spanning tree rooted in r

• edges of S join a node u to the first unrelated node after u in the clockwise preorder of T .

Such a partition can be computed in linear time.

Remark that the clockwise preorder of T is exactly the reverse order of the counterclockwise postorder of T . We denote by y(v) the index of v in a counterclockwise postorder of T . We consider an orientation of the edges of T and S such that all edges of T are oriented towards the root r and the edges (uv) of S are oriented from u to v if y(u) > y(v).

The tree T can be computed by Algorithm 1 presented in [START_REF] Bonichon | Canonical decomposition of outerplanar maps and application to enumeration, coding, and generation[END_REF]. A call Traversal(G, ∅, r) returns the tree T of G rooted in r, the second parameter stands for the current set of edges of the tree during the execution. For each node v of the outerplane graph G, we denote x(v) its index in counterclockwise preorder of T . Recall that y(v) is its index in counterclockwise postorder of T .

Lemma 1 Placing each node v of G at coordinates (x(v), y(v)) produces a planar rook-drawing of G.

Proof: By construction, the drawing D(G) obtained is a rook-drawing. It remains to show that this drawing is planar.

For a node v of G, let T v be the subtree of T rooted in v. Let G(v) be the subgraph of G induced by the nodes of T v . Let D(G(v)) be the drawing induced by the edges and nodes of G(v). The left branch of v in T v denotes the path between v and the first leaf found in a counterclockwise postorder of T v (see Fig. 4).

Let u and v be two nodes of G. The following observations are direct consequences of the definition of the x-and y-coordinates:

(i) If (uv) is an edge of S from u to v, then v is the first unrelated node of T after u in clockwise preorder of T , and thus the first node unrelated to u with y(v) < y(u).

(ii) If u is parent of v in T , then x(u) < x(v) and y(u) > y(v).

(iii) Let (uv) be an edge of S with y(u) > y(v). Then v is before u in counterclockwise postorder of T . Since v and u are unrelated, v is also before u in counterclockwise preorder of T , i.e. x(v) < x(u). Thus the edges of S are going down and to the left.

We now want to prove by induction the following proposition : D(G(u)) is planar and drawn in the subgrid [x(u), x(u)

+ |T u | -1] × [y(u) -|T u | + 1, y(u)].
When T u is reduced to a single node, the proposition clearly holds. Now assume the proposition holds for nodes having a subtree of depth at most k. Let u be a node with a subtree T u of depth k + 1. Denote by u 1 , ..., u m the children of u in clockwise order. Their subtrees in T are denoted T u1 , ..., T um . By induction hypothesis, the subtrees T u1 , ..., T um are placed in disjoint areas (see Fig. 4). Then D(G(u i )) and D(G(u j )) with i = j do not intersect. Thus T u is planarly drawn in the sub-grid [x(u), x(u)

+ |T u | -1] × [y(u) -|T u | + 1, y(u)].
We now prove that the edges of S joining nodes belonging to different subtrees do not create any crossing in D(G(u)). Let v and w be nodes from different subtrees linked by an edge of S from v to w. By remark (i), w is the first node unrelated to v with y(w) < y(v). So v and w are in consecutive trees, say T ui and T ui+1 , and w = u i+1 . Thus all edges of S joining T i to T i+1 have u i+1 as an end: edges of S join nodes of the left branch of u i to u i+1 . Then by remarks (ii) and (iii), the edges of S can not cross each other or edges of the tree T .

Thus D(G(u)) is planar and this concludes the proof.

Remark that as Andrews [START_REF] Andrews | A lower bound for the volume of strictly convex bodies with many boundary lattice points[END_REF] showed, a strictly convex grid drawing of a cycle of n nodes requires area Ω(n 3 ). Since a rook-drawing uses area O(n 2 ), it's not possible to produce strictly convex rook-drawing for the cycle for large n.

JGAA, 0(0) 0-0 (0) 7 Also note that the existence of n nodes both in rook position and in general position, i.e. such that no three nodes are colinear (see definition in [START_REF] Pach | Embedding a planar triangulation with vertices at specified points[END_REF]), would imply an algorithm for generating a rook-drawing of outerplane graphs (from [START_REF] Bose | On embedding an outerplanar graph in a point set[END_REF]). We do not know how to prove whether such a configuration exists. Remark though that the algorithm in [START_REF] Bose | On embedding an outerplanar graph in a point set[END_REF] has complexity O(n log 3 (n)), while the algorithm presented here is linear.

Polyline rook-drawing for planar graphs

As we proved that some plane graphs do not admit a planar rook-drawing with straight lines, we now relax the straight-line constraint and look at planar polyline rook-drawings. We first recall the definition of Schnyder woods.

Properties of Schnyder woods

Definition 1 (Schnyder [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF]) A Schnyder wood of a maximal plane graph G is a partition of the inner edges of G into three directed trees T 0 , T 1 , T 2 with the following properties:

• each tree T i is rooted on a distinct outer node v i ;

• the edges of each tree are directed toward the root;

• each inner node u of G has one parent in each T i , denoted P i (u);

• in counterclockwise order around each inner node, the outgoing edges are in T 0 then T 1 then T 2 ;

• each ingoing edge belonging to the tree T i is placed after the outgoing edge in T i+1 mod 3 and before the outgoing edge in T i-1 mod 3 in counterclockwise order around an inner node.

Let T i be the tree T i plus the edges (v i-1 , v i ) and (v i+1 , v i ). The orientation of edges around an inner node is shown in Fig. 5, where T 0 is drawn solid, T 1 is dotted, and T 2 is dotted-dashed. Throughout the paper, we call a 0-edge (respectively 1-edge, 2-edge) an edge belonging to the tree T 0 (resp. T 1 , T 2 ).

P 2 (u) P 0 (u) Lemma 4]) For every inner node u, P i-1 (u) and P i+1 (u) are unrelated to u in T i . Moreover P i-1 (u) (resp. P i+1 (u)) appears before (resp. after) u in the clockwise preorder and postorder of T i .

P 1 (u) u 2 0 1 0 2 1

Polyline rook-drawing algorithm

We here describe an algorithm to produce a planar polyline rook-drawing of a maximal plane graph of order n. The algorithm is inspired by an algorithm for polyline drawings proposed in [START_REF] Bonichon | Optimal area algorithm for planar polyline drawings[END_REF]. The original algorithm was designed to minimize the grid size and thus many rows and columns support several nodes. This new algorithm shares with the former the edge bending strategy, but the node placement is different.

Theorem 4 Every maximal plane graph G with n nodes admits a polyline planar rook-drawing D(G), which can be computed with Algorithm 2 in linear time. This drawing has n -3 bends.

In Algorithm 2 and later, ll 0 (u) denotes the last descendant met in a clockwise preorder of u in T 0 .

Algorithm 2: Planar polyline rook-drawing for a maximal plane graph G (T 0 , T 1 , T 2 ) ← Schnyder wood of G column order C ← clockwise preorder of T 0 row order R ← clockwise postorder of T 1 for u node of G do (x(u), y(u)) = (C(u), R(u)) for u inner node of G do if x(u) = x(P 0 (u)) + 1 then Bend edge (uP 0 (u)) at (x(u), y(P 0 (u)) + 1) if u = ll 0 (u) then Bend edge (uP 1 (u)) at (ll 0 (u), y(u)) Bend e = (v 1 v 0 ) at (x(v 1 ), 1) An example of the result of Algorithm 2 on a maximal plane graph is presented in Fig. 6b.

We first make the following observations on the placement of nodes after applying Algorithm 2:

• Since the nodes are placed according to their position in a preorder and a postorder, each row and column contains exactly one node. Thus D(G) is a rook-drawing.

• When u is a leaf of T 0 , then ll 0 (u) = u and this is the only case when the edge from u to P 1 (u) is drawn straight.

JGAA, 0(0) 0-0 (0) 9

v 0 v 1 v 2 A B C D E F G H I (

Number of bends.

Let k be the number of leaves in T 0 . By construction, T 0 , T 1 and T 2 contain each n -3 edges and n -1 nodes. The edges of T 0 are all bent, except one for each non-leaf node in T 0 . Thus n -3 -(n -1k) 0-edges are bent. The edges of T 1 are all bent, except k -1 (v 2 is a leaf in T 0 but is not a node of T 1 ). Thus n -3 -(k -1) 1-edges are bent. Finally, the edges of T 2 are never bent. The edges (v 0 v 2 ) and (v 2 v 1 ) are not bent, and the edge (v 0 v 1 ) is bent. Thus there are exactly n -3 -(n -1k) + (n -3 -(k -1)) + 1 = n -3 bends in the drawing of G.

Planarity.

We first describe in the following some structural properties of the drawing with Lemmas 3 and 4.

Lemma 3

In D(G), for each inner node u:

• x(P 0 (u)) < x(u) and y(P 0 (u)) < y(u): P 0 (u) is left and below u.

• x(P 1 (u)) > x(u) and y(P 1 (u)) > y(u): P 1 (u) is right and above u.

• x(P 2 (u)) < x(u) and y(P 2 (u)) > y(u): P 2 (u) is left and above u.

Proof: Recall that the x-coordinates are given by a clockwise preorder of T 0 and that the y-coordinates are given by a clockwise postorder of T 1 . Hence we have that x(P 0 (u)) < x(u) and y(P 1 (u)) > y(u). Applying Lemma 2 with i = 1 we get that P 0 (u), u and P 2 (u) appear in that order in the clockwise postorder of T 1 . Hence y(P 0 (u)) < y(u) and y(P 2 (u)) > y(u). Applying again Lemma 2 but this time with i = 0 we get that P 2 (u), u and P 1 (u) appear in

Figure 1 :

 1 Figure 1: Expansion of an aggregated node in a rook-drawing of a non-planar graph.

2 D

 2 . Auber, N. Bonichon, P. Dorbec & C. Pennarun Rook-drawings of Plane Graphs

Figure 2 :

 2 Figure 2: The tower plane graph T 6 .

Figure 3 :

 3 Figure 3: (a) and (b) Illustrations of the proof of Theorem 1. (c) A planar rook-drawing of T 6 .

DFigure 4 :

 4 Figure 4: (a) The decomposition of an outerplane graph G rooted in r into T (solid edges) and S (dotted edges). (b) The rook-drawing of G produced by applying Lemma 1. The subtree of T rooted in v is drawn in the gray area D(G(v)). The left branch of v is the path between v and w.

Algorithm 1 :

 1 Traversal(G, T, u) begin C ← {(uv) ∈ G | v / ∈ T } T ← T ∪ C for all edges (uv) ∈ Ctaken in the clockwise order around u do T ← Traversal(H, T, v) return T 6 D. Auber, N. Bonichon, P. Dorbec & C. Pennarun Rook-drawings of Plane Graphs

Figure 5 :

 5 Figure 5: Orientation around an inner node u in a Schnyder wood.

Figure 6 :

 6 Figure 6: (a) Schnyder wood of a maximal plane graph G. (b) The polyline drawing D(G) obtained by Algorithm 2.

Plane Graphs

. The area at the top-right hand side of v i is the area in which the subtree of v i in T 0 is drawn. that order in the clockwise preorder of T 0 . Hence we have that x(P 2 (u)) < x(u) and x(P 1 (u)) > x(u).

From Lemma 3 and the coordinates of bends chosen for the edges in Algorithm 2, we observe that the configuration around an inner node follows the scheme illustrated in Fig. 7.

Lemma 4 For every inner node u we have the following statements:

(i) every node v such that x(P 0 (u)) < x(v) < x(u) is a descendant of P 0 (u) in T 0 .

(ii) every node v such that x(u) < x(v) < x(P 1 (u)) is either a descendant of u in T 0 or y(v) < y(u) in D(G).

(iii) every node w such that x(P 2 (u)) < x(w) < x(u) is either a descendant of P 2 (u) in T 0 or y(w) < y(u) in D(G).

Proof: The first property is a direct consequence of the fact that the xcoordinates are given by the clockwise preorder of T 0 . Let v be a node such that x(u) < x(v) < x(P 1 (u)). By definition of x(v), either v is a descendant of u in T 0 , or it is in the area A delimited in the original graph G by the T 0 -paths (u, v 0 ) and (P 1 (u), v 0 ), and the edge (uP 1 (u)) in T 1 (see Fig. 8a). Note that v may belong to the path (P 1 (u), v 0 ). We consider the path P in T 2 from v to v 2 . Considering the relative orientations of the edges in the Schnyder wood, since v 2 is out of A, P has to intersect the border (u, v 0 ) of A to reach v 2 (even if v belongs to the T 0 -path (P 1 (u), v 0 ), its outgoing edge in T 2 heads into A). Let t denote the node at the intersection. There is a path in T 2 from v to t and a path in T 0 from u to t. By Lemma 3, y(v) < y(t) and y(t) < y(u), and thus y(v) < y(u).

A similar argument, exchanging the roles of T 1 and T 2 (see Fig. 8b), proves the third statement.

We now prove that the edges drawn do not cross. Lemmas 5 and 6 state such for the edges inside each tree T 0 and T 1 . Then we prove that edges from JGAA, 0(0) 0-0 (0) 11 different trees do not cross with Lemmas 7, 8 and 9. After that, we show that edges from T 2 do not cross pairwise with Lemma 10. Finally, drawing the edge (v 1 v 2 ) with a straight line does not create any crossing, since all nodes and bends are placed on the same side of the straight-line defined by the nodes v 1 and v 2 .

For each node u of G, recall that we denote ll 0 (u) the last descendant met in the clockwise preorder of u in T 0 .

Lemma 5

The edges of T 0 do not cross in D(G).

Proof: We prove by induction on the depth k of subtrees in T 0 the following proposition: in D(G), the subtree of a node u in T 0 , denoted T 0 (u), is drawn planarly in the subgrid [x(u), x(u) + |T 0 (u)| -1] × [y(u), n] (see Fig. 9).

The proposition clearly holds when k = 0. Assume the proposition holds for subtrees of depth at most k in T 0 . Let u be a node of G such that T 0 (u) is of depth k+1. Let u 1 , . . . , u m be the children of u (taken in the clockwise order). Nodes of T 0 (u) are consecutive in the clockwise preorder of T 0 and by Lemma 3, y(v) > y(u) for every node v of T 0 (u). Thus the drawing of the union of subtrees

By the induction hypothesis the edges of these subtrees are drawn in disjoint areas, hence the drawing of the union of the subtrees is planar. Moreover, by construction the edges joining u to u 1 , . . . , u m do not cross each other and lie in a region free of edges from the subtrees (each node u lies in the bottom row of its dedicated area). Hence the drawing of T 0 (u) is planar. By construction of the bends for the edges joining

Lemma 6 The edges of T 1 do not cross in D(G).

Proof: We prove by induction on the depth k of subtrees in T 1 the following proposition: in D(G), the subtree of a node u in T 1 , denoted T 1 (u), is drawn planarly in the subgrid [1, x(u)] × [y(u) -|T 1 (u)| + 1, y(u)] (see Fig. 10).

The proposition clearly holds when k = 0. Assume the proposition holds for subtrees of depth at most k in T 1 . Let u be a node of G such that T 1 (u) is of depth k +1. Let u 1 , . . . , u m be the children of u (taken in the clockwise order). Nodes of T 1 (u) are consecutive in the clockwise postorder of T 1 and by Lemma 3, x(v) < x(u) for every node v of T 1 (u). Thus the drawing of the union of subtrees

By the induction hypothesis, the edges of these subtrees are drawn in disjoint areas, hence the drawing of their union is planar.

Let now prove that the edges joining u and u 1 , . . . , u m do not cross each other. Recall that (u u) is bent at coordinates (x(ll 0 (u )), y(u )). Let u and u +1 be two consecutive children of u. Let us show that the bends (uu ) and (uu +1 ) are placed at positions with increasing y-coordinates and decreasing x-coordinates. By Lemma 3, y(u ) < y(u +1 ), thus the bends have increasing y-coordinates. We now prove that x(ll 0 (u +1 )) ≤ x(ll 0 (u )). By definition of the x-coordinates, all descendants of an inner node t in T 0 are placed on consecutive columns at the right of t. Since y(u ) < y(u +1 ), by contrapositive of Lemma 4.(ii), either u +1 is a descendant of u in T 0 or x(u +1 ) < x(u ). Suppose u +1 is a descendant of u in T 0 . By Lemma 3 and the definition of the x-coordinates, x(ll 0 (u +1 )) ≤ x(ll 0 (u )). Suppose now x(u +1 ) < x(u ). Thus all descendants of u +1 in T 0 have abscissas between x(u +1 ) and x(u ), hence x(ll 0 (u +1 )) ≤ x(ll 0 (u )).

Then the bends for the edges (uu ) are placed at positions with increasing y-coordinates and decreasing x-coordinates. Thus the edges joining u and u 1 , . . . , u m do not cross each other. These edges can not cross edges of a subtree of u in T 0 either, as each node u lies in the bottom row of the area dedicated to the drawing of T 0 (u) and the bent of the edge (u u) lies in the right-most column of this area. Hence the drawing of T 1 (u) is planar.

Lemma 7

The edges of T 0 and T 1 do not cross in D(G).

JGAA, 0(0) 0-0 (0) 13

Figure 10: Illustration of the proof of Lemma 6. The area at the bottom-left hand side of u i is the area in which the subtree of u i in T 1 is drawn.

Proof: Let (wt) be a 1-edge. By Lemma 3, x(w) < x(t) and y(w) < y(t). Let (uv) be an edge of T 0 . If x(w) > x(u) or y(w) > y(u), then the edges (wt) and (uv) can not cross each other. Suppose then that x(w) < x(u) and y(w) < y(u).

Suppose first that x(t) > x(u) . Since x(w) < x(u) < x(t) and y(w) < y(u), by Lemma 4.(ii), u is a descendant of w in T 0 . Thus v is also a descendant of w in T 0 . But then the bent of (wt) avoids any crossing.

Suppose then that x(t) < x(u) . If y(v) < y(w), then the bend of uv avoids any crossing. Thus assume y(v) > y(w). By Lemma 4.(i), if x(v) < x(w), then w is a descendant of v in T 0 , contradicting y(v) > y(w). So x(w) < x(v) < x(t) and by Lemma 4.(ii), v is a descendant of w in T 0 , and so is u. By definition of the x-coordinates, all descendants of w in T 0 are consecutive to w and before t in the x-order, a contradiction with x(t) < x(u).

Lemma 8

The edges of T 0 and T 2 do not cross in D(G).

Proof: Let (wt) be a 2-edge. By Lemma 3, x(t) < x(w) and y(t) > y(w). Let (uv) be an edge of T 0 . If x(w) < x(v) or y(v) > y(t), then the edges (uv) and (wt) do not cross each other. Similarly, if x(u) < x(t) or y(u) < y(w), the edges do not cross either. So assume that x(v) < x(w), y(v) < y(t), x(t) < x(u) and y(w) < y(u).

If x(u) < x(w) , by Lemma 4.(iii), u is a descendant of t in T 0 . Since v is the parent of u in T 0 , v is also a descendant of t in T 0 . Hence by Lemma 3, y(v) > y(t); a contradiction. If x(u) > x(w) , then x(v) < x(w) < x(u) and by Lemma 4.(i), w is a descendant of v in T 0 . Thus (uv) avoids w and there is no crossing.

Lemma 9

The edges of T 1 and T 2 do not cross in D(G).

Proof: Let (uv) be a 2-edge and (wt) a 1-edge. By Lemma 3, x(u) > x(v), y(u) < y(v), x(t) > x(w) and y(t) > y(w). Assume x(t) > x(v), y(t) > y(u), x(w) < x(u) and y(w) < y(v), or (uv) and (wt) may not cross. If x(t) < x(u) (see Fig. 11a), then x(v) < x(t) < x(u). Since y(t) > y(u), by the contrapositive of Lemma 4.(iii), t is a descendant of v in T 0 . Then the orientation of the edges around t implies that either (uv) and (wt) do not cross, or (wt) also cross the T 0 -path (t, v), contradicting Lemma 7.

If x(u) < x(t), then x(w) < x(u) < x(t). u is not a descendant of w in T 0 (otherwise the bend of (wt) would prevent the crossing). Thus by definition of x(u), u is in the area A delimited in the original graph G by the paths (w, v 0 ) and (t, v 0 ) in T 0 , and the edge (wt) in T 1 (see Fig. 11b). Note that u may belong to the path (t, v 0 ) in T 0 . We consider the path P in T 2 from u to v 2 . Considering the relative orientations of the edges in the Schnyder wood, since v 2 is out of A, then P has to intersect the border (w, v 0 ) of A to reach v 2 (even if u is on the path (t, v 0 ), its outgoing edge in T 2 heads into A). Let z denote the intersection. By Lemma 3, y(z) < y(w). z is a parent of u in T 2 and thus a parent of v in T 2 (we may have z = v). Thus by Lemma 3, y(z) ≥ y(v) and thus y(w) > y(v), which is a contradiction.

Lemma 10

The edges of T 2 do not cross in D(G).

Proof: Let (uv) and (wt) be edges of T 2 . Suppose they cross each other. Thus x(w) > x(v), y(w) < y(v), x(t) < x(u) and y(t) > y(u). Since the two edges play similar roles, we can suppose without loss of generality that x(t) > x(v). Then x(v) < x(t) < x(u) and y(t) > y(u), and by Lemma 4.(iii), t is a descendant of v in T 0 . But then the edge (wt) would cross a 1-edge in the path of T 1 joining v to v 1 , contradicting Lemma 9.

Conclusion

In this paper, we observed that no maximal planar graph but the tower graphs admit a planar straight-line rook-drawing. On the other hand we showed that every outerplane graph admits a planar straight-line rook-drawing. A natural question is: are there other classes of plane graphs that all admit a planar JGAA, 0(0) 0-0 (0) 15 straight-line rook-drawing? A plane graph that has a triangular outer face and admits a planar straight-line rook-drawing is necessarily a subgraph of the tower plane graph we described earlier. However, if we consider plane graphs with an outer face with at least 4 vertices, it seems that many of them should admit such a drawing. Then, plane graphs that do not contain non-facial triangles, as, for instance, quadrangulations or 4-connected triangulations with outer face of degree at least 4, are possibly good candidates for admitting a planar rookdrawing.

We also showed that every plane graph admits a planar polyline rookdrawing with at most n -3 bent edges. Even if this number of bends is reasonable, one could ask if a linear number of bends is needed for allowing a planar rook-drawing of any planar graph.

Another interesting question would be to consider relaxed rook-drawing in which each row and column contains at most one node (and no longer exactly one node). Clearly every plane graph admits a planar relaxed rook-drawing: it suffices to consider a straight-line planar drawing of the plane graph and add a tiny perturbation to nodes sharing some coordinates. This naive approach produces drawings with a huge number of empty columns and rows, which is not suitable in practice. Hence the good question would be: does every plane graph admit a planar relaxed rook-drawing with a small (i.e. linear or sublinear) number of empty rows and columns? There are no evidence yet that even a constant number of empty rows and columns would not suffice.