V Mahtout

Milanés

F Nashashibi
email: fawzi.nashashibi@inria.fr

F Navas

D Gonzalez

Youla-Kucera Based Lateral Controller for Autonomous Vehicle I. Mahtout 1,2 , F. Navas 3 , D. Gonzalez 3 , V. Milanés 1 and F. Nashashibi 2 Abstract-This paper presents the design and implementation of a novel lateral control approach. The proposed control strategy is based on Youla-Kucera parametrization to switch gradually between controllers that are designed separately for big and small lateral errors. The present approach studies the critical problem of initial lateral error in line following. It ensures smooth and stable transitions between controllers and provides a smooth vehicle response regardless of the lateral error. For an initial validation the present work was tested in simulation, implementing a dynamic bicycle model. It has also been tested in real platforms implementing an electric Renault ZOE, with good results when activating the system at different lateral errors. autonomous vehicles Switched controllers parametrization I. INTRODUCTION Automated vehicles are getting more and more attention because of their potential to improve drivers' life, insuring road safety, increasing highway capacity or reducing carbon emission. When it comes to conceive autonomous vehicles, assuring its stability plays a key role. The vehicle motion stability is assured by a control process that is capable to interpret high level decision (i.e. follow a line, avoid an obstacle) into actions according to a given trajectory. Vehicle control can be divided in longitudinal (i.e. the ability to regulate vehicle speed by controlling brake and throttle actuators) and lateral (i.e. vehicle steering regulation to track and follow a reference path) controllers. This paper is focused on the latter one. Steering control has been widely studied in the last three decades. The first demonstration was carried out in "No Hands Across America" event in mid 90s. Carnegie Mellon University's researchers [START_REF] Jochem | Life in the fast lane: The evolution of an adaptive vehicle control system[END_REF] presented Navlab car that completed around 5000km. The steering wheel was controlled by correcting lateral offset and heading error. Curvature was used as feedforward in the control loop. The vehicle was semi-autonomous because the throttle and brake pedals were controlled by the driver. In 1998 Prof.Broggi et al [START_REF] Broggi | The ARGO autonomous vehicles vision and control systems[END_REF] demonstrated the ARGO vehicle, that conducted itself along the Italian highway network. The steering system was based on a proportional controller to correct the vehicle deviation with respect to the center lane. In 2005, Stanley vehicle won the second DARPA (Defense Advanced Research Projects Agency) Grand Challenge [START_REF] Thrun | Stanley: The robot that won the DARPA Grand Challenge[END_REF]. Its steering controller was based on a nonlinear feedback of the cross-track error by using estimated velocity, UKF pose and measured steering wheel angle. This approach works well for lower speed, but it neglected the steering column dynamics. In 2012, BRAiVE vehicle was demonstrated in the Intercontinental Autonomous Challenge, developed by Prof. Broggi's team. Its lateral controller included two levels: first, setting a target point in the desired trajectory, at a look ahead distance that vary with respect to the vehicle speed, then converting the curvature in the control point to steering value, by inverting the vehicle dynamic model. To avoid jerky performance, variation in curvature lower than ±5% was not considered. The vehicle was able to drive in urban areas (i.e. roundabouts). In the same year, the university team of Prof. Sunwoo won the autonomous car competition organized by Hyundai Motor in Korea [START_REF] Jo | Overall reviews of autonomous vehicle a1-system architecture and algorithms[END_REF]. The basic idea of the lateral controller is that the vehicle always moves along Ackerman geometry, except for straight movement. The vehicle showed good performance in mixed circuits. In 2013, Mercedes cooperated with different research labs to make an autonomous journey in memorial Berta Benz road. The lateral controller included two parts: first, a feedforward part that calculates the desired yaw rate using trajectory curvature at a target point. This one is set at a look-ahead distance depending on the vehicle speed, in order to compensate the steering column dynamics; second, a feedback part, that minimizes the lateral displacement in order to stabilize the lateral position. Finally, the required steering wheel angle is computed from the desired yaw rate using an inverse stationary single track model. For steady state accuracy, a steering angle offset observer is used to compensate both deviation in the inverse single track model as well as a steering angle offset in the steering actuator [START_REF] Ziegler | Making Bertha driveAn autonomous journey on a historic route[END_REF]. The above described systems are part of automated steering wheel demonstration well known in the literature. However, other implementations have been proposed. In [START_REF] Marino | Nested PID steering control for lane keeping in autonomous vehicles[END_REF] a nested PID controller is used to control the vehicle steering angle. In [START_REF] Hima | Trajectory tracking for highly automated passenger vehicles[END_REF] an H ∞ approach is used. A sliding mode controller is validated by experimental results in [START_REF] Tagne | Higher-order sliding mode control for lateral dynamics of autonomous vehicles, with experimental validation[END_REF]. In [START_REF] Onieva | Automatic lateral control for unmanned vehicles via genetic algorithms[END_REF] human steering skills are used to emulate manual driving. Lateral controller is based on fuzzy logic approach fed by informations about the car state while human is driving, via genetic algorithms. In [START_REF] Tan | Design of a high-performance automatic steering controller for bus revenue service based on how drivers steer[END_REF], inspired by drivers mechanism, authors developed a T&C controller (Target and Control Driver Steering Model). The generated steering rate is simply the target angle error (angle between the vehicle heading and the target point set at a look-ahead distance) scheduled by a gain feedback, it has been successfully implemented on a bus revenue service as a simple linear control loop. In [START_REF] Luan | Design and Field Testing of a Lane Following Control System with a Camera Based on T&C Driver Model[END_REF] the same approach has been validated on experimental car. The review of the different techniques shows two different approaches when dealing with steering control: 1) the use of complex vehicle model that includes all dynamics, and design suitable control structure that handles nonlinear behaviors and model parameter variations. In this case, the computation time becomes large for real time operation [START_REF] Borrelli | MPC-based approach to active steering for autonomous vehicle systems[END_REF]; and 2) the use of linear controller based on a simplified vehicle model, and tuned for a defined use case (i.e. lane keeping, lane changing), which can't satisfy steering performance in different driving situations. Automated steering systems should be able to address any circumstances ranging from starting the vehicle fully stopped to activating the function with a significant error with respect to the reference trajectory or performing lane changes. For covering all this situations, a single controller will not satisfy all conditions. This paper proposes a control structure that handles any significant lateral deviation. This deviation can be caused either by a first system activation, avoidance maneuver or even a localization discontinuity. The proposed control structure can cover the above by switching gradually between two different controllers: a lane-tracker controller for one case and a lane change controller for situations with significant lateral errors. Both controllers are implemented in a reconfigurable control structure, based on Youla-kucera parametrization. This control parametrization ensures stability while switching between controllers. In [START_REF] Tay | High performance control[END_REF][2][3] authors used Youla-Kucera parametrized structure in different applications, and presenting encouraging simulation and experimental results. Both controllers are based on T&C approach, for the fact that it's a linear SISO controller already validated by experimental tests. This paper is organized as follows. Sections II introduces the Youla-Kucera controller structure and its basis mathematical developments. In Section III, the vehicle model is presented with the control strategy and the stability analysis. Section IV presents the simulation results . Section V presents experimental platform and results. Some concluding remarks and future work directions are given in the end .

II. YOULA-KUCERA CONTROLLER CONFIGURATION

This section presents the basis on the proposed technique for controller switching. It relies on Youla-Kucera parametrization of all stabilizing controllers for a given plant (see [START_REF] Tay | High performance control[END_REF], [START_REF] Niemann | An architecture for implementation of multivariable controllers[END_REF], [START_REF] Onieva | Automatic lateral control for unmanned vehicles via genetic algorithms[END_REF] and [START_REF] Niemann | Parameterisation of extended systems[END_REF]). The Youla-Kucera parametrization is based on the doubly coprime factorization. Let's consider a plant G ∈ R m * n , mapping n inputs to m outputs.

y = Gu, y ∈ R m and u ∈ R n .
Different controllers K i ∈ R n * m can be designed to stabilize G. Stable switching between those controllers is possible using Youla-Kucera parametrization, the plant G and controllers K i need to be factorized to apply the parametrization.

A. Doubly Coprime Factorization

The plant model and controllers matrix transfer functions are factorized to a product of a stable transfer function matrix and a transfer function matrix with a stable inverse as follows:

G = NM -1 = M-1 Ñ N, M, Ñ, M ∈ RH ∞ (1)
K i = U i V -1 i = Ṽ -1 i Ũi U i ,V i , Ũi , Ṽi ∈ RH ∞ ( 2
)
This factorization is named coprime when the two transfer function matrix have no commun zeros in |z| > 1 or ℜ(s) > 0 in continuous case. Knowing that K i stabilizes G, the coprime factors must satisfy the following Bezout equations:

Ṽi M -Ũi N = I, (3)
MV i -ÑU i = I, (4)
Or equivalently, and considering ( 1) and ( 2) the double Bezout identity :

Ṽi -Ũi -Ñ -M M U i N V i = M U i N V i Ṽi -Ũi -Ñ -M = I 0 0 I (5)
To calculate those factors [START_REF] Tay | High performance control[END_REF], we consider a state space descriptions of G and K i :

G : A B C D K i : A i B i C i D i (6)
Under the controllability assumption of the pairs (A, B) and (A i , B i ), constant stabilizing state space feedback matrix respectively F and F i can be constructed, in that (A + BF) and (A i + B i F i ) have all eigenvalues within the unity circle. State space descriptions of stable coprime factors for G and K i are given as follows : (further details are in [START_REF] Tay | High performance control[END_REF])

M U i N V i =     A + BF 0 B 0 0 A i + B i F i 0 B i F C i + D i F i I D i C + DF F i D I     (7) Ṽi -Ũi -Ñ M =     A + BY D i C BYC i -BY BY D i B i ZC A i + B i ZDC i -B i ZD B i Z F -Y D i C -YC i Y -Y D i ZC -(F i -ZDC i ) ZD Z     (8)
where Y = (I -D i D) -1 and Z = (I -DD i ) -1 . Then coprime factors can be calculated, using the standard transformation from state space description to transfer function matrix.

B. Youla-Kucera Parametrization

According to Youla-Kucera, all stabilizing controllers for a given plant G can be written as a function of a stable filter Q i (see [START_REF] Tay | High performance control[END_REF]):

K i = K(Q i ) = (U i-1 + M i-1 Q i )(V i-1 + N i-1 Q i ) -1 (9) = ( Ũi-1 + Q i Mi-1 )( Ṽi-1 + Q i Ñi-1 ) -1 (10)
where, Q i is a stable transfer function with appropriate inputoutput dimensions, called Youla-Kucera parameter. Thanks to this parametrization, two controllers are involved in the same control structure as shown in Fig. 1. For each stable matrix Q i , controller reconfiguration from K i-1 to K i is carried out by setting K i = K(Q i ). The stability of the closed loop is guaranteed by the stability of Q i and to perform a smooth transition, a scalar factor γ ∈ [0, 1] is added to scale Q i . When γ = 0 the control signal is completely generated by K i-1 . 0 < γ < 1 generates a control signal combination of K i-1 and K i responses. When γ = 1 the control signal is completely generated by K i , more details and proof are in [START_REF] Tay | High performance control[END_REF]. The steering controller switching proposed in this paper uses the lateral error as parameter to deal with γ, playing a key role in the final control applied. The design of γ is detailed further.

Using two stable controllers K 1 and K 2 , and including γ, the parametrized controller is realized as follows:(see [START_REF] Stoustrup | Plug & play control: Control technology towards new challenges[END_REF])

K = (U 1 + M 1 γQ)(V 1 + N 1 γQ) -1 (11)
with:

Q = Ũ2 V 1 -Ṽ2 U 1 ( 12
)
Other control structures using Youla-Kucera parametrization can be deducted (see [START_REF] Stoustrup | Plug & play control: Control technology towards new challenges[END_REF] for further details).

III. CONTROLLER DESIGN

The goal of the controller is to develop a system able to deal with not only trajectory following but also with any other circumstance. When passing from manual to autonomous driving (i.e. autonomous driving activation), the vehicle may have an initial error in function of vehicle position with respect to the reference trajectory. The ability to handle this kind of situation can be extended to lane-change maneuver or avoidance maneuver, meaning that it will be hard to handle all circumstances with a single controller. To perform automated lane changing and lane tracking maneuvers, two different steering controller behaviors are required.

Figure 2 shows step response of the expected controller for each situation. In lane-tracking task (solid blue line), the controller must provide fast response to track changes in the desired trajectory (i.e. curved line). Overshoots are tolerated because its maximum value is equal to the initial lateral error, which is small in this case (the vehicle is already in the lane). While in lane-changing case (solid red line), the initial lateral error is significant. Thus, a smooth response is required, less overshoots are provided while compromising the rising time. To cover both situations in one control structure, the proposed solution is to design a switched controller. This one is based on Youla-Kucera parametrization to guarantee stable switching (see section II). The control structure is illustrated in Fig. 3. It includes two controllers: lane-changing controller C 1 (dashed red box); lane-tracking controller C 2 (dashed blue box). The switching between controllers is handled by the lateral error between the vehicle and the desired trajectory. Further details on controller design and vehicle model are given below. The vehicle lateral dynamics is described in a state-space form, using the bicycle model [START_REF] Rajamani | Vehicle dynamics and control[END_REF] as follows:

Ẋv = A v X v + B v u v Y v = C v X v ( 13
)
where the state vector is:

X v = y v v y ψ v ω v y v , v y , ψ v
, ω v are the vehicle lateral position, lateral velocity, yaw angle and yaw rate respectively, u v = δ f t is the steering angle in the front tire. The system matrix A v ,B v and C v are described below:

A v =      0 1 v x 0 0 -(C f +C r ) mv x 0 -aC f +bC r mv x -v x 0 0 0 1 0 -a 2 C f +b 2 C r I z v x 0 -(C f +C r ) I z v x      (14)
B v = 0 C f m 0 aC f I z T C v = 0 0 0 1
where C f , C r , a, b, m, I z and v x are cornering stiffness of front and rear tires, distance from front and rear axle to the center of gravity of the vehicle, vehicle mass, yaw moment of inertia and the longitudinal velocity respectively. The vehicle transfer function is deduced from the state space model as follows:

G v = C v (Is -A v ) -1 B v

B. Steering actuator:

The steering actuator is mainly represented by a steering column and an Electric Power System (EPS) that is regulated by a desired steering angle δ c calculated by the controller. It is modeled by a 3 rd order transfer function G act . Thus, the general plant to be controlled is G = G v G act .

C. Lateral controller:

The design of C 1 (lane-changing controller) and C 2 (lanetracking controller) is based on T&C approach [START_REF] Tan | Design of a high-performance automatic steering controller for bus revenue service based on how drivers steer[END_REF]. The controllers output is a steering wheel angle δ c computed according to a yaw rate error ω r = ω vω d , the desired yaw rate is:

ω d = vρ road
where ρ road is the road curvature in the target point (set at a look-ahead distance d), and v is the longitudinal velocity.

δ c (s) = -k s d 2v + 1 s + v ds 2 ω r (s) (15)
Thus,

C(s) = -k s s 2 + 2 v d s + 2( v d 2 ) 2 v d s 2 (16)
k and d are designed in order to achieve the expected behaviors of C 1 and C 2 , specifically :

• Lane-changing controller C 1 : In this case initial lateral error is significant. The controller must be smooth to avoid overshoots and uncomfortable sensation in the vehicle. For solving so, target point is set to 30m (i.e. d value). • Lane-tracking controller C 2 : In this case, fast response is required. According to [START_REF] Tan | Design of a high-performance automatic steering controller for bus revenue service based on how drivers steer[END_REF], the closer is the target point, the smaller is the tracking error. For doing so, look-ahead distance is fixed to d = 15m. The appropriate feedback gain k is identified using basic pole placement technique. Both controllers are implemented in a parametrized structure (see Fig. 3). As explained in section II, the resultant Youla-Kucera controller switches between C 1 and C 2 without losing the stability of the closed loop. The parameter γ is in charge of the controllers' switching based on the vehicle lateral error with respect to the trajectory as follows:

• When the lateral error > 3m, the adequate controller is C 1 so γ = 0. • When the lateral error < 0.2m, the adequate controller is C 2 so γ = 1. Between the two limits γ changes gradually depending on the lateral error values as shown in Fig. 4. Then γ changes

D. Stability Analysis

The closed loop stability of the full control structure is presented on this section. For doing so, the root locus response of the control structure for different γ values is presented in Fig. 5.

It's notable in the root locus that all the poles during the transition are in the unity circle, which means that the whole system is stable. For 0

< γ < 1, poles positions remain in {poles[G,C 1 ] ∪ poles[G,C 2 ]}.

IV. SIMULATION RESULTS

To validate the algorithm, a given scenario was implemented using the vehicle model previously described (see section III for details). A straight lane is used as reference trajectory. All simulations are started with an initial deviation of 3 meters from the reference trajectory and the vehicle speed was set to 10m/s. The vehicle controlled by C 2 (lane-tracker controller) is the first to reach the desired lane, but Figure 7 shows that its steering wheel angle is the highest with a brutal steering rate, that causes uncomfortable sensation in the vehicle, the vehicle controlled by C 1 (lane-change controller) has the smoothest steering angle and the lowest steering rate but it takes around 150 m to reach the lane, while the vehicle controlled by the proposed approach (YK controller) has a correct behavior, it reaches the desired lane at the same time that the one controlled by C 2 while maintaining smoothness of steering angle and steering rate, it satisfies the required steering performance .

V. EXPERIMENTAL VALIDATION

The proposed approach was tested on an electric Renault ZOE that has been modified for allowing steering computed control.

To validate the proposed control structure, many scenarios have been tested. In each test the vehicle was removed manually from the desired lane and the autonomous mode was started at a given lateral error as shown in Fig. 8. The manual driven phases are denoted by M. The vehicle speed is set to 10m/s. In Figure 8 it's shown that the controller switched between

Fig. 1 .

 1 Fig. 1. Youla-Kucera control structure

Fig. 2 .

 2 Fig. 2. Desired control behavior

Fig. 3 .

 3 Fig. 3. Control structure

Fig. 4 . 2 <

 42 Fig. 4. The switching parameter γ can be mathematically expressed by the equation below:

  Zeros appear and move to compensate C 1 or C 2 effects. The closer γ to one, the closer the zeros to poles of [G,C 1 ], and respectively the closer γ to zero the closer the zeros to poles of [G,C 2 ]. In Fig.5 a part of the root locus is zoomed, zeros and poles are represented respectively by circles and crosses. It is shown that zeros move between [G,C 1 ]'s poles and [G,C 2 ]'s poles with respect to γ.

Fig. 5 .Figure 6

 56 Fig. 5. Dynamics compensation

Fig. 6 .

 6 Fig. 6. Response for constant speed v=10m/s

Fig. 7 .

 7 Fig. 7. Steering wheel angle and steering wheel rate

Fig. 8 .

 8 Fig. 8. Experimental results

ACKNOWLEDGMENT

Authors express their gratitude to the RENAULT research department for its support in developing experimental tests. This paper reflects solely the views of the authors and not necessarily the views of the company they belong to.

Autonomous vehicles should be able to address and respond to any circumstance, meaning that the steering system should be able to perform different maneuvers (i.e. lane changing, lane tracking, avoiding objects), while maintaining stability, control performance and passengers comfort. This paper proposed a Youla-Kucera based control structure including two controllers: one for tracking the desired trajectory and one for lane changing case. Experimental results have proven that the proposed control structure is a good way of dealing with this situations. It enhances performances of only using a single controller for two cases. Errors are significantly reduced, and even with a deviation of 5m the vehicle reached the desired lane smoothly. The switching between controllers was gradual and stable. Further works will be oriented to include more driving situations to enlarge controller capabilities and ensure high performance in any circumstance without loosing steering system stability or compromising passengers comfort. Finally converging to a system able to control the vehicle at full range speeds.


Roy Pea

Robb Lindgren

Joseph Rosen

Computer-Supported Collaborative Video Analysis

Learning

Video can serve as a powerful medium for analyzing interactions involved in learning activities, for capturing records of teaching for uses in professional development, and for learners to construct or interact with videos expressively, but there have been many barriers to its collaborative uses. The DIVER Project is tackling core problems in advancing computer-supported collaborative video analysis. DIVER establishes a unique video platform for users to control a "virtual camera window" on a computer for guiding noticing to parts of a video of interest as the video is playing-then to text annotate these moments, and publish them on the web for further collaborative analysis. Every DIVER user-researcher, teacher, or learner-can thus express their visual and interpretive point of view on a video, providing an important and accessible tool for making a difference in our research and education. Ongoing studies of learning research and higher education applications using DIVER are discussed.

Introduction

Video has been an unnatural medium to support collaborative activity in a way that provides persistent records of the insights that collaborators develop together. Text provides for collaborative writing, but when researchers or other learner groups want to work with video as a medium for interpretation, sharing, commenting, their collective work is not well enabled. Our challenge is making computer-supported collaborative video analysis (CSCVA) into a commonplace collective practice, whether face to face or in distributed groups connected with mediating technologies. We are a long way from collective practices of video analyses in the learning sciences or for education. We describe the socio-technical design problems facing CSCVA, in order to explain our rationale for and experiences with DIVER as a platform to support video collaborations for several ongoing scientific and educational activities. We then consider how workflow scenarios with DIVER are meeting the CSCVA sociotechnical design challenges with which we began.

Background and Significance of the CSCVA Problem

The advancement of augmentation tools for human activities has built on several decades of socio-technical design theory and practices. [START_REF] Scacchi | Socio-technical design[END_REF] notes how: "Socio-technical design is concerned with advocacy of the direct participation of end-users in the information system design process. The systems include the network of users, developers, information technology at hand, and the environments in which the systems will be used and supported. The process includes the design of the human-computer interface and patterns of human-computer interaction." With this view in mind, we ask, what are the primary socio-technical design issues for CSCVA that heed these concerns? We characterize seven primary socio-technical issues that constitute core challenges affiliated with CSCVA. Virtually all the concerns to be outlined relate to the fundamental problem of coordination of attention, interpretation, and action between multiple persons. [START_REF] Clark | Using language[END_REF] described as "common ground" what it is people seek to achieve in the work they do to coordinate what they are attending to and/or referring to, so that when comments are made, what these comments refer to can be appropriately inferred, or elaborated. In the learning sciences, "common ground" is usually used to examine collaborative or teaching learning discourse and pointing, bodily orientation and joint visual regard to the focus of a conversation that is being analyzed for studies of learning or teaching (e.g., [START_REF] Barron | When smart groups fail[END_REF]. But it is not sufficient only to focus on the non-technology mediated aspects of common ground-once we look at inscriptional systems (e.g., [START_REF] Latour | Visualization and cognition: Thinking with eyes and hands[END_REF]) that lay down and layer symbolic records such as text, diagrams or other paper-based representations, they, too, become a focus of pointing and joint visual regard, and introduce new problems as transient referents. One may want to refer to an earlier moment when only a part of a mathematical diagram was present, for that is what one wishes to establish common ground around. This common ground concept must extend from the face-to-face situation of co-presence and its static properties to the situation of distributed conversationalists and the dynamics of representations, as when these representations are computer-enabled (e.g., [START_REF] Pea | Seeing what we build together: Distributed multimedia learning environments for transformative communications[END_REF]. One often needs to refer to specific states of information display when using computer tools, so establishing a common ground for discourse and sense-making in a digital realm is important, too, including the dynamic medium of video. Considering these concerns, our seven socio-technical design issues for CSCVA are:

1) The problem of reference. How is it that I as someone analyzing video can refer to a specific time-space region of a dynamic video record in a way that 'lasts' beyond the here and now? In the here and now, I can point my finger to a display on which a video record is playing, encircle the topic for my comment, and thereby highlight what I will be commenting on. Traditionally, the video medium has not provided the capability for a watcher of the video to point in such a way that records the locus of reference for a time-shifted or space-shifted (remote) audience of the watcher's referring act. It is noteworthy how this is important even for an individual analyzing a video as well; absent a record of what I have pointed at, I may later not be able to recall what aspects of the video I found interesting, problematic, compelling, or whatever, or to which a comment I wrote down can be attached. So solving the video reference problem can also serve as a personal memory aide, not only a collaborative one.

2) The problem of attentional alignment. The related problem of co-reference, or 'attentional alignment', has to do with how it is that I as someone analyzing video and engaging in a referential act to some part of it can establish that the person(s) to whom I am addressing this referring act is attending to the video segment that I refer to. [START_REF] Goodwin | Gestures as a resource for the organization of mutual orientation[END_REF] highlights gesture's deictic uses in efforts to organize mutual orientation. When the conditions for achieving such co-reference have been secured, I have been successful in establishing attentional alignment. The reason that this coordination is important is that any consequent dialog about my video referent can lead to misunderstanding and other conversational troubles if my listener believes I am referring to something other than what I intended to refer to.

3) The problem of creating video "immutable mobiles." In characterizing the power of written texts, [START_REF] Latour | Visualization and cognition: Thinking with eyes and hands[END_REF] developed the influential concept of inscriptions as external representations of ideas that serve as "immutable mobiles" with these key properties: 1) Inscriptions are mobile; 2) They are immutable when they move; 3) They are made flat; 4) The scale of the inscriptions may be flexibly modified; 5) They can be cheaply reproduced and spread; 6) They can be reshuffled and recombined; 7) One may superimpose different images of totally different origins and scales; 8) They can be made part of a written text; and 9) Their 2-D character allows them to merge with geometry. Although his concerns were to provide a novel explanatory account of how science and technology took hold so powerfully, Latour's theory has had considerable influence in the digital documents world (e.g., [START_REF] Levy | Scrolling forward: Making sense of documents in the digital age[END_REF], and its implications for conceptualizing video as an inscriptional medium are important. How shall videorecordings become immutable mobiles? [START_REF] Stevens | Seeing tornado: How video traces mediate visitor understandings of (natural?) phenomena in a science museum[END_REF].

4) The problem of effective search, retrieval and experiencing of collaborative video work. The work life of video analysis with videotapes was challenging enough, with the physical tape media to index and store, possibly in many different versions as derivative tape collections were made of interesting moments. If we can solve the problems of pointing to video, establishing attentional alignment, and creating video as an immutable mobile medium, we generate a few new problems. As users become technically enabled to point to, annotate, and foster attentional alignment to portions of a videorecord, they will generate a vast array of persistent video-plus-pointing-plus-commentary digital objects. How will users be able to effectively solve the information retrieval problem, and quickly find what they want and experience these video-anchored interpretive acts, the moments that matter to them?

5) The problem of permissions. Access and control issues turn on appropriate assignment of permissions, with two broad classes of situation at hand. One concerns video analyses when we work with video that may have sensitive human subjects conditions. Research participants (or the parents of minors) in from institutions funded by federal research grants provide informed consent to specific conditions of use for research videorecords of their activities. These consent forms and procedures for ensuring confidentiality of subject data, or other terms of consent (such as in what contexts the video can be shown) are reviewed and approved by Human Subjects Institutional Review Boards in a researcher's institution. For this reason, it is important to have only approved individuals view such video. In a second situation, there are issues concerning digital rights management, common for film or television works but also applicable to user-generated video content. One may wish to allow only certain individuals to view video, to create video annotations, or to make remixes of video assets. 6) Establishing a productive workflow of collaborative activity. This issue is really about how to best tap the collective intelligence of a group engaged together in collaboratively analyzing video recordings. canonical interaction analysis methodology for group work on video (e.g., [START_REF] Jordan | Interaction analysis: Foundations and practice[END_REF], there has tended to be a hierarchical rather than heterarchical organization of analysis: a group leader controls the video selection and play, picks participants in the physical meeting to make observations, audiorecords the group's work, mines the groupwork audiotape, and then creates or directs the creation of a video analysis informed by the deliberations of the group. In such a workflow there are many idle times when observations or contributions from group members are not being tapped or recorded for comparison and reflection, and multiply rich interpretive accounts that could be developed from the collective set of insights of the group are not developed. What new kinds of research activity structures are opened up with CSCVA which are distinctive from face-to-face video analysis?

7) The problem of establishing coherent multi-party video-anchored discourse. Consider a faceto-face conversational interaction, as in a seminar, when the rules of discourse that sustain turn-taking and sense-making as people converse are familiar. Discourse analysis and studies of conversation have made great progress in uncovering the systematics of turn-taking, speech acts, and accounting for the semantic and pragmatic coherency of discourse across turns and speakers (e.g., Heritage & [START_REF] Goodwin | Conversation analysis[END_REF][START_REF] Heath | Disembodied conduct: Interactional asymmetries in video-mediated communication[END_REF]. Intrinsic to these social activities in work meetings and academic seminars are uses of media that include paper used by individuals for note-taking, a whiteboard for writing and drawing, and increasingly, a public screen for displaying computer presentations. In an academic setting, video, film and audio recordings may also be played. Traditionally these are used asymmetrically, as the facilitator/instructor prepares these records to make a point or to serve as an anchor for discussion, and controls their play during the discourse. Computer-facilitated meetings for doing video analysis-where each participant has a computer and is network-connected with other participants and to external networks for information access, search and retrieval-bring new challenges beyond non-technically mediated meetings in terms of managing a coherent group discourse.

Illustration of Troubles to be Resolved

This paper attempts to make these issues concrete by discussing them in terms of ongoing efforts to engage in two novel practices with face-to-face and distributed CSCVA: (1) in several undergraduate courses; and 2) for learning sciences research concerning informal learning.

Undergraduate Courses Utilizing Video

Over the past year we have worked with a number of college-level instructors at large researcher universities who had all in the past employed video-based discussions into their lessons. These courses included a film studies course and a Japanese language course at a West Coast university, and a film production course at a midwestern university. In each setting the goal was to present students with one or more video artifacts and have the students generate insights using an analytic frame provided by the instructor. For example, students in the film studies course looked at two video clips, the "Crispin's Day" speech in the film adaptation of Shakespeare's Henry V from the 1989 version directed and played by Kenneth Branagh, and from the 1944 film version of the same play directed and played by Sir Laurence Olivier. The instructor's objective was to have students comparatively analyze how the same text was translated to film by two different directors/actors. Students previously had to make the comparison for this assignment by reconstructing the film events from memory for a written essay. In this scenario, students are faced with the reference problem-in making their argument they have no way to explicitly refer to an important aspect of the video film clip (e.g., an aggressive gesture by Branagh at a point where Oliver is subdued) that they may have noticed upon first viewing.

In the film production course students are also asked to analyze video clips, but in this case the clips are those created by fellow students. Individuals are responsible for making their own experimental film available for others to view, and for providing feedback on at least two other student films. How valuable one student's feedback is for another depends largely on the issue of attentional alignment-how effective is the critiquing student in conveying to the film's creator the focus of the critique? For example, one student shot a music video for his film project and another student noted: "This is my favorite sequence. The transition between band members works well with the music and beat." Absent a record of what precisely the critiquing student was looking at when she made this comment, it carries little meaning. The film production course also exemplifies the problem of search and retrieval. As the critique of other students' films is a class assignment, the course instructor must be able to efficiently access the corpus of comments, sorted by author or target film, so as to judge the quality of the feedback.

In the Japanese language course the instructor's desire is to engage her 10-12 students in a discussion about the dialog styles used by the actors in a set of video clips she has collected over the years. Specifically she seeks to elicit insights from her students that will illustrate a sophisticated understanding of conversational Japanese; thus she uses a diverse set of sources from pop culture artifacts (e.g., Japanese soap operas and anime) to videotaped interviews with native Japanese speakers. Although these insights are not formally assessed, it is important to the instructor that all students contribute to the discussion and that these insights build off one another. Structuring a productive multi-party discourse of this type centered around a number of video records can be difficult for an instructor to accomplish given the lack of precedent for video anchored conversation and the requisite patterns of discourse.

Learning Sciences Research: Collaborative video analyses

In our NSF Science of Learning Center (LIFE), we are studying informal learning of mathematics in family situations. Our research group of two faculty and three graduate students is investigating the contexts and activities in which middle school age learners and their families engage in mathematical problem solving. In interview sessions and observations lastly roughly two hours, we are working with over 30 families that represent California's diversity to identify the contexts and situations that families participate in which serve as locations for mathematical learning and practice. We digitize our video records and seek to develop coding categories and analyses that foreground the nuances of family math in situ. We seek to describe the resources family members use for recognizing and solving problems, characterize the structure of their mathematical activities, and analyze the social conditions and arrangements for their family-based mathematics practices. We used a semi-structured interview protocol organized around mathematically relevant contexts to center on activities that most families engage in, while allowing families to give us their particularized versions of how they accomplish each life task (including technology use, and systems of representing mathematical relationships). For our analytic work, we wanted to do both face-to-face meetings reviewing videorecords, and independent work that can contribute to the group collaboration whenever we can access the data and build interpretations and coding activities concerning it. We also will be doing collaborative analyses of our data with researchers at U.Washington, UCSC, and other institutions. We need good solutions to the seven socio-technical design challenges to CSCVA to make this work as productive as possible.

THE DIVER Software Environment for Video Collaboration. DIVER is a software environment first developed for research uses of panoramic video records [START_REF] Pea | The DIVER™ project: Interactive digital video repurposing[END_REF]). As we have developed a web-enabled DIVER allowing for distributed access and annotation of digital video records from consumer digicams, our focus has shifted to supporting collaborative video analysis and emerging prospects for "digital video collaboratories" (Pea, in press). We are putting DIVER to work and evolving its capabilities in support of collaborative video analysis for many research and educational activities. We call the central work product in DIVER a "dive" (as in 'dive into the video'). A dive consists of a set of XML metadata pointers to segments of digital video stored in a database and their affiliated text annotations. In authoring dives on streaming videos via any web browser, a user is directing the attention of others view the dive to see what the author sees; it is a process we call guided noticing [START_REF] Pea | The DIVER™ project: Interactive digital video repurposing[END_REF]. To make a dive using DIVER a user logs in and chooses any video record that has been made available in the searchable database. The video selected can be viewed using standard video controls. As the video plays, a user can manipulate a virtual camera viewfinder (the yellow rectangle in the figure) on top of the video to focus in on a specific area of interest. By clicking the MARK button, the user saves a reference to a specific point in space/time within the video and places it within a data container-a single panel that resides inside the DIVER "worksheet" in the webpage and signified with an image thumbnail. Once the mark has been added to the worksheet, the user can comment on that mark by entering text in the panel. Panels can also be created by clicking on the RECORD button, creating a pointer to an entire segment of the video and storing the path taken by the virtual viewfinder during that segment. Like a MARK, a recorded clip can be annotated by adding text inside the respective panel on the worksheet. The DIVER user can replay the recorded video segment or see the recorded mark by clicking on its thumbnail image.

Assuming they have appropriate permissions, multiple users can access a dive simultaneously, with each user able to add new panels or make comments on a panel that another user created. Users are notified in real-time when another user has made a contribution to the dive and they can view any changes by clicking on the update button. Thus, users may be either face to face in a meeting room, or connected to the same webpage remotely via networking, as they build a collaborative video analysis. In principle and in practice, there is no need for the users to be watching the same portions of the video at the same time; as the video is streamed to them through their web-browser, they may mark and record and comment at their own pace and as a function of their own interests. Collaborative video analysis activity using DIVER can be as planful or emergent as participants choose to make it; constraints on focus, intent, duration of sessions, and so on are not built into the technology but a matter of negotiated social practice.

CSCVA Workflow with DIVER: Addressing the socio-technical design issues

With a brief sketch of DIVER, and these examples where research or learning groups have been using DIVER in support of collaborative video analysis, we now may reflect on the workflow steps and the activity systems in which the DIVER technologies are playing instrumental roles. We have been learning a great deal about the unique affordances of this video analysis platform for the nature of such work, and unearthing new challenges.

1) The problem of reference. DIVER provides a virtual camera viewfinder for a user to inscribe a video region of interest as their referential act [START_REF] Stevens | Video Traces: Rich media annotations for teaching and learning[END_REF] use a pointing gesture). Text annotation is used for free-field text interpretations or coding categories to the referred-to video content. Virtual pointing to a video region and affiliated annotation provide the communication infrastructure for a dive author to make link-addressable references to the dynamic medium of video in their conversations.

2) The problem of attentional alignment. The method of virtual pointing to a circumscribed part of the space-time continuum of a video record enables distributed users to focus their attention on the same regions of the video for their interpretive work. With DIVER's web-based methods, users can align attention to the parts of the video that matter to them for their discourse whether they are synchronously or asynchronously connected, as the points into video streams are persistent XML metadata.

3) The problem of creating "immutable mobiles" from video recodings. Latour's concept of written texts as immutable mobiles reviewed earlier has considerable applicability in considering how a dive establishes a video immutable mobile. The digital inscriptions provided by the lightweight metadata of a dive are mobile, immutable when they move (in that they preserve their character across locations, platforms, browsers), are made "flat" (2-D), can be flexibly modified in scale (through projection), can be cheaply reproduced and spread (thanks to Internet standards), allow one to "superimpose different images of totally different origins and scales" (in their digital document forms), can be made part of a written text (through hyperlinking to dives), and may be merged with geometry thanks to their two-dimensionality.

4) The problem of effective search, retrieval and experiencing of collaborative video work. The time dimension of video needs to be unlocked. With any volume of video, this is an enormous problem and a barrier to greater video use. DIVER provides Google-like search for any term or phrase used in the full text of annotations, title, or user name. A DIVER search returns a list of dive panels with the search term or phrase highlighted and the video keyframe for that panel. In terms of retrieval, clicking on such a list item or keyframe opens up the affiliated dive and enables the user to view the precise video regions in space/time to which the searched-for terms were applied. The value of the metadata tagging of a user community for research videos will grow tremendously as multiple researchers work with a data set and develop cumulative analyses across projects. In the informal math learning work, we are finding it easy to compile the accumulated annotations of our multi-party research group on specific phenomena such as uses of props, symbol manipulation, emotion terms, and the like and then to create composite codebooks that are dives resulting from all exemplars of a given type, identified across multiple researchers, and now able to be experienced in a sequential remix of the clips of a given type from a new Dive.

5) The problem of permissions. DIVER provides access to video records and their dives only for users granted permissions to certain rights. Administrative tools enable the formation of groups, and the establishment of whether specific video assets and dives can be viewed, copied, edited or deleted. 6) Establishing a productive workflow of collaborative activity in video analyses. Some of the most dramatic changes in DIVER-enabled collaborative video analysis concern this design problem. Whereas sequential turn taking is required in collaborative face-to-face video analysis work practices, parallel analyses can be carried out with DIVER, to cumulative effects. Multiple individuals can be streaming the same video file, looking at different parts of it at the same time, and making their dive recordings and annotations without control from the single group leader customary in video interaction analysis sessions. Stopping and starting the video being played, setting in and out points to segments to be annotated, selecting different segments to compare in an analysis, can all be carried out in parallel when DIVER is used by a distributed group of analysts. DIVER CSCVA thus shifts control from the group facilitator to individual participants, who can play the entire source or can use the cues from one another's ongoing analyses to focus their attention on subparts of the video. In relation to scientific inquiry processes, there is the added benefit that, as one posts conjectures as DIVER annotations concerning the interpretations of an event, multiple analysts can seek out confirmation or disconfirming evidence elsewhere in the video data records relating to that conjecture, and then post such links as either comments in the dive of the individual making the conjecture or as new panels in that dive, pointing to other video evidence that is available.

7) The problem of establishing coherent multi-party video-anchored discourse. Our experiences with DIVER for video analysis in collaborative groups have not yet made much headway on this dimension. We have largely used DIVER in an asynchronous manner for collaborative group work of our informal family math learning video records, or face to face meetings where a projected screen is used to coordinate group attention and workgroup participants take turns by ordinary social conventions in selecting dives they would like to share or ask questions about from other members of the workgroup.

Conclusion

The DIVER system distinctively enables what we call "point of view" authoring of tours of existing video materials in a way that supports sharing, collaboration, and knowledge building around a common ground of reference. We are in the early days of documenting its uses as a digital video collaboratory platform and addressing the seven socio-technical design challenges for computersupported collaborative video analysis.

Acknowledgements. DIVER™, WebDIVER™, Dive™ and "Guided Noticing"™ are trademarks of Stanford University for DIVER software and services with patents pending. DIVER has been supported by grants from the National Science Foundation (#0216334, #0234456, #0326497, #0354453) and the Hewlett Foundation.


Sylvain Lazard

William J Lenhart
email: wlenhart@williams.edu

Giuseppe Liotta
email: giuseppe.liotta@unipg.it

On the Edge-length Ratio of Outerplanar Graphs

Keywords: Graph drawing, outerplanar graphs, edge-length ratio

We show that any outerplanar graph admits a planar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. This result is tight in the sense that for any > 0 there are outerplanar graphs that cannot be drawn with an edge-length ratio smaller than 2 -. We also show that this ratio cannot be bounded if the embeddings of the outerplanar graphs are given.

Introduction

The problem of computing a planar straight-line drawing with prescribed edge lengths has been addressed by several authors, partly for its theoretical interest and partly for its application in different areas, including VLSI, wireless sensor networks, and computational geometry (see for example [START_REF] Battista | Angles of planar triangular graphs[END_REF][START_REF] Doherty | Convex optimization methods for sensor node position estimation[END_REF][START_REF] Held | Combinatorial optimization in VLSI design[END_REF][START_REF] Savarese | Robust positioning algorithms for distributed ad-hoc wireless sensor networks[END_REF]). Deciding whether a graph admits a straight-line planar drawing with prescribed edge lengths was shown to be NP-hard by Eades and Wormald for 3-connected planar graphs [START_REF] Eades | Fixed edge-length graph drawing is NP-hard[END_REF]. In the same paper, the authors show that it is NP-hard to determine whether a 2-connected planar graph has a unit-length planar straightline drawing; that is, a drawing in which all edges have the same length. Cabello et al. extend this last result by showing that it is NP-hard to decide whether a 3-connected planar graph admits a unit-length planar straight-line drawing [START_REF] Cabello | Planar embeddings of graphs with specified edge lengths[END_REF]. In addition, Bhatt and Cosmadakis prove that deciding whether a degree-4 tree has a planar drawing such that all edges have the same length and the vertices are at integer grid points is also NP-hard [START_REF] Bhatt | The complexity of minimizing wire lengths in VLSI layouts[END_REF].

These hardness results have motivated the study of relaxations and variants of the problem of computing straight-line planar drawings with constraints on the edge lengths. For example, Aichholzer et al. [START_REF] Aichholzer | Graph drawings with relative edge length specifications[END_REF] study the problem of computing straight-line planar drawings where, for each pair of edges of the input graph G, it is specified which edge must be longer. They characterize families of graphs that are length universal, i.e. that admit a planar straight-line drawing for any given total order of their edge lengths.

Perhaps one of the most natural variants of the problem is to compute planar straight-line drawings where the variance of the lengths of the edges is minimized. See for example [START_REF] Di Battista | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF], where this optimization goal is listed among the most relevant aesthetics that impact the readability of a drawing of a graph. Computing straight-line drawings where the ratio of the longest to the shortest edge is close to 1 also arises in the approximation of unit disk graph representations, a problem of interest in the area of wireless communication networks (see, e.g. [START_REF] Chen | Separability and topology control of quasi unit disk graphs[END_REF][START_REF] Kuhn | Unit disk graph approximation[END_REF]).

Discouragingly, Eades and Wormald observe in their seminal paper that the NP-hardness of computing 2-connected planar straight-line drawings with unit edge lengths persists even when a small tolerance (independent of the problem size) in the length of the edges is allowed. To our knowledge, little progress has been made on bounding the ratio between the longest and shortest edge lengths in planar straight-line drawings. We recall the work of Hoffmann et al. [START_REF] Hoffmann | Quality ratios of measures for graph drawing styles[END_REF], who compare different drawing styles according to different quality measures including the edge-length variance.

In this paper we study planar straight-line drawings of outerplanar graphs that bound the ratio of the longest to the shortest edge lengths from above by a constant. We define the planar edge-length ratio of a planar graph G as the smallest ratio between the longest and the shortest edge lengths over all planar straight-line drawings of G. The main result of the paper is the following.

Theorem 1. The planar edge-length ratio of any outerplanar graph is strictly less than 2. Also, for any given real positive number , there exists an outerplanar graph whose planar edge-length ratio is greater than 2 -.

Informally, Theorem 1 establishes that 2 is a tight bound for the planar edge-length ratio of outerplanar graphs. The upper bound is proved by using a suitable decomposition of an outerplanar graph into subgraphs called strips, then drawing the graph strip by strip. The lower bound is proved by taking into account all possible planar embeddings of a maximal outerplanar graph whose maximum vertex degree is a function of .

We note here that for any given outerplanar topological embedding of an outerplanar graph G, the algorithm of Theorem 1 computes an embedding preserving drawing of G whose planar edge lengthratio is strictly less than 2. Therefore, Theorem 1 naturally raises the question of whether a bound can be proven for every (not necessarily outerplanar) topological embedding of G. The next theorem answers this question in the negative. The plane edge-length ratio of a planar embedding G of a graph G is the minimum edge-length ratio taken over all embedding-preserving planar straight-line drawings of G.

Theorem 2. For any given k 1, there exists an embedded outerplanar graph whose plane edge-length ratio is at least k.

The remainder of the paper is structured as follows. We prove Theorems 1 and 2 in Sections 2 and 3, respectively. We shall assume familiarity with basic definitions of graph planarity and of graph drawing [START_REF] Di Battista | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF] and introduce only the terminology and notation that is strictly needed for our proofs.

Edge-length ratio of outerplanar graphs

We prove in this section Theorem 1. It suffices to establish the result for maximal outerplanar graphs. To show that the edge-length ratio of a maximal outerplanar graph G is always less than 2, we consider any outerplanar topological embedding of G and decompose the dual G * of this embedding into a set of disjoint paths, which we call chains. Each chain corresponds to some sequence of adjacent triangles of G. The set of chains inherits a tree structure from G * , and we use this structure to direct an algorithm that draws each of the chains proceeding from the root of this tree down to its leaves. We formalize these concepts below.

Given an edge e on the outer face of some outerplanar topological embedding of G and an orientation for this edge, we label the source of e as v - 0 and the sink as v + 0 . The edge e is incident to a unique triangular face of G, which we label as T 0 ; we label the third vertex of T 0 as v 1 . The orientation of e induces an orientation of the edges of G such that the edges of each face form an oriented cycle. Refer to Figure 1(a-b) (to reduce the visual clutter, not all edge orientation are shown). We define constructively the chain C e as the maximal sequence T s , T s+1 , . . . , T 0 , . . . , T t of faces of G, with s 0 t, such that (i) for 1 i t, T i shares edge v i-1 v i with T i-1 (where v 0 refers here to v + 0 ) and its third vertex is labelled v i+1 and (ii) for s i -1, T i shares edge v i+2 v i+1 with T i+1 (where v 0 refers here to v - 0 ) and its third vertex is labelled v i . Rougly speaking, this means that considering a walk from T 0 to T t (resp. to T s ) in the chain of triangles, the exit edges after leaving T 0 alternate between right and left, starting with right if T 0 is oriented clockwise (as in Figure 1(a)) and starting with left otherwise (as in Figure 1(b)). If T 0 is oriented clockwise, we say that C e is a clockwise chain; C e is a counterclockwise chain otherwise.

v + 0 T 0 T 1 T 2 T 3 T -1 T -2 T -3 v 1 v - 0 v 2 v 3 v 4 v 5 v -1 v -2 v -3 e v 6 v -4 T -4 T 5 v + 0 T 0 T 1 T 2 T 3 T 4 T -1 T -2 T -3 v 1 v - 0 v 2 v 3 v 4 v 5 v -1 v -2 v -3 e v -5 v -4 T -4 T -5 (a) (b) T 0 v 1 e (c)
The edges of C e can be partitioned into two sets S e and L e which we refer to as short edges and long edges, respectively (long edges will be drawn with length 1 and short edges with length in ( 1 2 , 1)). S e consists of edges of C e whose vertex indices differ by 1 and L e consists of all other edges of C e (i.e., those whose vertex indices differ by 2, along with e). See, for example Figure 1(a) where the short edges of C e are dashed, whereas the long edges of C e are solid. Note that all the (oriented) long edges of C e are boundary edges of the union of the triangular faces of C e and that they can be partitioned into edge e and four oriented paths, two of which ending at v 1 and the two others ending at v + 0 and v - 0 respectively (see Figure 1(a-b)); the short edges of C e are all the internal edges plus the (only) two boundary edges that are not long edges (e.g., edges v -3 v -4 and v 5 v 6 in Figure 1(a)).

Consider now the (not connected) outerplanar graph G -S e obtained by removing the edges of S e 1 1 1 1 from G. Each 2-connected component of G -S e is either an edge of L e or it is an outerplanar graph G e having exactly one edge e of L e on its outer face. Note that the initial choice of orientation for e induces an orientation for all edges of G e . We recursively decompose each 2-connected component G e of G -S e into chains by using the procedure described above, starting from the oriented edge e . We call the set of chains so constructed a chain decomposition of G. This naturally defines a chain-decomposition tree: The root of the tree is the chain C e and its children are the chains C e for e ∈ L e ; the next level of the tree consists of the chains C e with e ∈ L e , and so forth. Note that the chain decomposition of G and its corresponding chain-decomposition tree are uniquely determined once edge e is oriented.

1 2 + ε 1 2 + ε 1 2 + ε 1 2 + ε 1 2 + ε 1 2 + ε 1 2 + ε 1 2 + ε T 0 T 1 T 2 T 3 T 4 T t v 1 v - 0 v 2 v 3 v 4 v 5 v t-1 v t v t+1 x v + 0 e 1 2 1 2 1 2 1 2 θ 1 1 2 + ε 1 1 2 + ε T 0 1 1 1 2 + ε 1 2 + ε 1 2 + ε 1 1 2 + ε 1 2 + ε T -1 T -2 T -3 T s v 1 v + 0 v -1 v -2 v -3 v s+2 v s+1 v s v - 0 e
In order to compute a drawing of G with edge length ratio strictly less than 2, we perform a pre-order visit of the chain-decomposition tree, drawing each chain as we visit the correspond node of the tree. The correctness of the algorithm depends on a specific method for drawing a single chain.

Denote by x a vector oriented along the positive x-axis and, given an oriented segment s in the plane, denote by s its supporting vector. Define the right strip of segment s, denoted by S(s, x), as the half-infinite strip bounded by s and by the two infinite rays emanating from the endpoints of s in the direction x. Lemma 3. Given a clockwise (resp. counterclockwise) chain C e with n vertices and an oriented segment s of length 1 such that the angle θ = ∠(x, s) is in (π -θ 0 , π) (resp. in (π, π + θ 0 )) with θ 0 = arccos(1/4) ≈ 75.5 • , there exists a planar straight-line drawing of C e such that: (i) The oriented edge e is drawn as s, (ii) the drawing is contained in the strip S(s, x) and lies outside (or on the boundary of) the right strips of all long edges of C e ; (ii) all long edges have length 1 and all short edges have length in ( 1 2 , 1); (iii) all long edges are drawn with an orientation such that their angle with x is in (π -θ 0 , π + θ 0 ) and distinct from π. Moreover, such a drawing can be computed in O(n)-time in the real RAM model.

Proof. Assume that the chain C e is clockwise (the proof for counterclockwise follow the same reasoning). Refer to Figure 2. Let v + 0 and v - 0 be the vertices of edge e in the chain C e , and let T 0 be its incident triangle. T 0 is either adjacent to zero, one, or two triangles of C e . We handle these three cases in turn. If T 0 is the only triangle in C e , then we simply draw T 0 in S(s, x) as an isosceles triangle with e drawn as s and with its third vertex drawn so that its two edges have length l, where 1 2 < l < 1. Assume now that T 0 is adjacent to a triangle T 1 of C e . In this case a more careful positioning of of v 1 is required. We first draw edge v + 0 v 2 of T 1 as a unit-length segment in direction x. As long as v 1 is positioned outside of the disks of radius 1 2 centered at v - 0 , v + 0 , and v 2 , the edges from each of these vertices to v 1 will have length greater than 1 2 (see top half of Figure 2). By also placing v 1 close enough to the midpoint of e, the edges v 1 v - 0 and v 1 v + 0 will have lengths less than 1. Furthermore, by placing v 1 inside S(s, x), the edge v 1 v 2 will have length less than 1 because ∠v 2 v + 0 v 1 < θ 0 = arccos(1/4), which is the largest angle in an isosceles triangle having side lengths 1, 1, and 1 2 . Assuming that T 0 , . . . , T i-1 have been drawn for some i > 1, T i is drawn by positioning v i+1 one unit distant from v i-1 in direction x. The result is that each T i is congruent to T 1 and so the edge-length ratio of C e is less than 2. At this point, all of the unit-length segments, except for e, lie on the two rays in direction x emanating from v + 0 and v 1 . By rotating these rays a very small amount towards one another, we can preserve the lengths of the unit-length segments while ensuring that all of the remaining segments have lengths in the range ( 1 2 , 1). Finally, suppose that T 0 has two adjacent triangles. Draw each T i , i > 0 as in the previous case. Now draw the T i , i < 0 in a similar fashion: Place vertex v i one unit distant from v i+2 in direction x. Then, as above, all of the unit length edges of the triangles T i , i < 0 will lie on the two rays in direction x emanating from v 1 and v - 0 , and these two rays can be rotated slightly towards each other while maintaining the length of the unit-length edges and ensuring that the other edges still have lengths in the range ( 1 2 , 1). See the bottom of Figure 2. However, we need to ensure that v 1 can be placed so that both triangle T 1 and triangle T -1 can simultaneously satisfy the required edge-length conditions: Namely, that edges v -

0 v + 0 , v 1 v -1 , and v + 0 v 2 are all unit-length, while edges v 1 v 2 , v + 0 v 1 , v 1 v - 0 , and v - 0 v -1 all have lengths in the interval ( 1 2 , 1
). The only one of these conditions that is not already guaranteed by the construction of T 0 , . . . , T t is that v - 0 v -1 has length less than 1. However, placing v 1 sufficiently close to the midpoint of e also ensures that the length of v - 0 v -1 is smaller than 1. Finally, the computation of the locations of the vertices can each be computed in constant time in the real RAM model, giving a run-time linear in the size of the chain.

We call the drawing defined by Lemma 3 a U-strip drawing of C e and we now use it to prove the following lemma, which implies the upper bound of Theorem 1. Lemma 4. A maximal outerplanar graph with n vertices admits an outerplanar straight-line drawing such that the length ratio of the longest to the shortest edges is strictly less than 2. The drawing can be computed in O(n) time assuming the real RAM model of computation.

Proof. Let G be a maximal outerplanar graph with any outerplanar topological embedding. An embeddingpreserving drawing of G is computed as follows. First, select and orient an edge e of the outer face of G, then compute the chain-decomposition tree T of G, from e. We will draw the chains of T in pre-order. Let C e be the chain associated with the root of T . Choose arbitrarily an oriented line segment s of length 1 in the plane such that the angle ∠(x, s) is in (π -θ 0 , π) if C e is clockwise and in (π, π + θ 0 ) otherwise. Apply Lemma 3 to compute a U-strip drawing of C e . Now, consider a child C e of C e in T . Then e is a long edge of C e and thus, by Lemma 3, it is drawn as a segment s e of length 1 that forms an angle with x that is in (π -θ 0 , π + θ 0 ) \ {π} and such that the drawing of C e does not intersect the interior of the strip S(s e , x). If the angle that s e forms with x is in (π -θ 0 , π) (resp. (π, π + θ 0 )), the triangle T 0 of C e that contains e is oriented clockwise (resp. counterclockwise); indeed, since the drawing of C e does not intersect the interior of S(s e , x) by Lemma 3, the triangle of C e that contains e is oriented counterclockwise (resp. clockwise). Hence, we can apply Lemma 3 to draw C e in the strip S(s e , x); in fact, the entire sub-tree of T rooted at C e will v be recursively drawn in this strip as the algorithm progresses. See Figure 1(c) for an illustration of the drawing of the first two levels of T.

The result is an outerplanar straight-line drawing in which all long edges in the chains of the decomposition are drawn with length 1 and all short edges have length in ( 1 2 , 1). If we assume that the input is provided to the algorithm in the form of a doubly-connected edge list [START_REF] Muller | Finding the intersection of two convex polyhedra[END_REF], then a chain-decomposition tree for G can be computed in linear time. Also, since by Lemma 3 each chain can be drawn in time proportional to its length, the algorithm runs in O(n) time in the real RAM model.

We now prove a lower bound on the edge length ratio of outerplanar graphs, which together with Lemma 4, proves Theorem 1.

Lemma 5. For any > 0 there exists a maximal outerplanar graph whose planar edge length ratio is greater than 2 -.

Proof. Let the length of the longest edge be 1. We show that, for any value > 0, there exists a maximal outerplanar graph G such that in any planar straight-line drawing of G, the length of the shortest edge must be smaller than 1 2-. Let us rewrite 1 2-as 1 2 + δ, where δ = 2(2-) . In any planar straight-line drawing of a maximal outerplanar graph such that the longest edge has length 1 and the shortest edge has length at least 1 2 + δ, the area of every triangular face cannot become arbitrarily small, and it has a lower bound that depends on the value δ. More precisely, the minimum area of such a triangle is obtained when one of its edge has length 1 while the other two have length 1 2 + δ: Indeed, observe first that a triangle is trivially not of minimal area if at most one of its edges has minimum length. Now, if two of its edges have minimum length α = 1 2 + δ, with θ denoting the angle between these edges, the triangular area is α cos(θ/2) • α sin(θ/2) = 1 2 α 2 sin(θ), which increases for θ in [0, π/2] and decreases in [π/2, π]. So the minimum area is obtained when the third edge takes an extreme value, 1 or α = 1 2 + δ. Furthermore, if δ is small enough, the minimum area is obtained when the third edge has length 1 because, when δ tends to zero, the triangular area tends to zero if the third edge has length 1 and it tends to the area of the equilateral triangle of edge length 1/2 otherwise. Thus, by Heron's formula (the area of a triangle whose edge lengths are a, b, c is s(s -a)(s -b)(s -c) with s = a+b+c 2 ), the area of any triangular face under these assumptions is at least

1 2 √ δ + δ 2 .
Let k be a positive integer and consider a fan graph F with a vertex v of degree k +2; G is constructed by adding k + 1 triangular faces to F as follows: for each edge e of F not incident to v, add a new vertex adjacent to both vertices of e. Refer to Figure 3. We call these non-fan triangles pendant triangles. Observe that in any planar straight-line drawing Γ of G, independently of whether all vertices of Γ appear on a common face or not, we have that the drawing has at least k area-disjoint pendant triangles, since any pendant triangle that contains another triangle must contain the entire graph. Also, since the longest edge in the drawing has length 1 and since every vertex has graph theoretic distance at most 2 from vertex v, we have that Γ lies inside a disk D of radius 2 centered at v. The number ν of area disjoint triangles that can be packed inside D such that every triangle has area at least Thus, for any k > 8π √ δ+δ 2 , any planar straight-line drawing of the maximal outerplanar graph G where the length of the longest edge is 1 requires at least one edge having length shorter than 1 2 + δ.

Embedded outerplanar graphs

We prove in this section Theorem 2, starting with a straightforward lemma. Refer to Figure 4. Consider a triangle ABC whose longest edge is AB and let a, b, c be the lengths of the edges opposite to vertices A, B, C, respectively. Let D be the point on segment AB such that the distance from A to D and from D to B are respectively a-b+c + d, which is less than the perimeter of ABC minus half the length of its smallest edge.

Proof. The first claim that both triangles have equal perimeter is trivial. Assuming without loss of generality that edge BC, of length a, is the shortest edge, the second claim states that a+b+c 2 +d < a+b+c-a 2 , which is equivalent to 2d < b + c and which follows from the fact that d is smaller than both b and c (to see this, note that the longest segment that is incident to C and inside ABC is the edge CA, which implies that d < b, but b c by assumption).

We now prove Theorem 2. We construct a family G n of outerplanar graphs having planar embeddings G n with unbounded plane edge-length ratio ρ(G n ), that is such that ρ(G n ) → ∞ as n → ∞. Each G i , i 0, has a set of 2 i+1 so-called distinguished edges, and G i , i > 0, contains G i-1 as a subgraph. Refer to Figure 5(a). G 0 is a single triangle, with any two of its edges defined as distinguished. G i+1 is constructed from G i by adding, for each distinguished edge e of G i , a new vertex v e that is adjacent to both vertices of e; the newly added edges are the distinguished edges of G i+1 . There is only 1 embedding of G 0 ; the embedding G 1 of G 1 is obtained by putting the two vertices of G 1 \ G 0 in the inner face of G 0 . For i > 1, the embedding G i+1 of G i+1 is defined by placing each new vertex v e in the (unique) triangular face of G i having e on its boundary (see Figure 5(a)).

Assume for a contradiction that for each G n there is a planar straight-line drawing Γ n of G i that preserves the embedding described above, and that, for some ρ * 1, ρ(Γ n ) ρ * for all n 0. By scaling the drawing, we can assume without loss of generality that the longest edge of Γ 0 has length 1; thus the edges in any Γ n have lengths at most 1 and at least 1 ρ * . Consider a triangular face T created in the construction of G i for some i > 0 and refer to Figure 5(b). It consists of a distinguished edge e of G i-1 along with the vertex v e in G i \ G i-1 adjacent to e. The two edges e 1 and e 2 incident with v e are distinguished edges of G i , so in G i+1 each of them will form a triangle with some new vertex, say v 1 and v 2 , respectively, and both new vertices will be in the face T . We consider two cases depending on whether e is the longest edge of T .

If e is the longest edge of T , consider the partition of T in two triangles T 1 and T 2 , as in Lemma 6. At least one of T 1 and T 2 contains the triangle (e 1 , v 1 ) or (e 2 , v 2 ); say T 1 contains triangle (e 1 , v 1 ) as in Then the perimeter of triangle (e 1 , v 1 ) is less than that of T 1 , which is less than the perimeter of T minus half the length of the shortest edge of T , by Lemma 6. But all edges of the Γ i have lengths at least 1 ρ * , so the perimeter of triangle (e 1 , v 1 ) is smaller than that of T minus 1 2ρ * . Now, if e is not the longest edge of T , then one of e 1 or e 2 must be. Let e denote this longest edge, then after the construction of G i+1 , e must be the longest edge of the (new) triangle T formed by e and v e because the edges of T are contained in T , and thus their lengths are at most the length of the longest edge of T , which is e . Thus, in the construction of G i+2 , one of the new triangles formed, by similar application of Lemma 6, has a perimeter that is at least 1 2ρ * shorter than the perimeter of T , which itself is shorter than the perimeter of T .

In each of the two cases we have identified a triangle, either in G i+1 or in G i+2 , whose perimeter is shorter than that of T minus 1 2ρ * . Since the perimeter of T is at most 3, repeating this process 6ρ * times results in a triangle whose perimeter is negative, which is a contradiction and concludes the proof of Theorem 2.

Conclusion

We conclude this paper by listing some open questions. One is whether better bounds on the planar edge-length ratio can be established for subfamilies of outerplanar graphs; for instance, the planar edgelength ratio of a bipartite outerplanar graph is 1 and this actually holds for the larger class of the duals of weak pseudo line arrangements [START_REF] Eppstein | Algorithms for drawing media[END_REF]Thm. 3]. One other interesting class is that of triangle-free outerplanar graphs: it is not hard to see that if all faces of an outerplanar graph have five vertices, a unit edge length drawing may not exist; however, the planar edge length ratio for this family of graphs could nonetheless be smaller than the one established in Theorem 1.

Another problem is to extend the result of Theorem 1 to families of non-outerplanar graphs. For example it would be interesting to determine whether the planar edge-length ratio of 2-trees is bounded by a constant. We conjecture that this is, in fact, not the case, but it is not clear how to establish this using our current techniques.

Finally, a natural question is to determine the complexity of deciding whether an outerplanar graph admits a straight-line drawing where the ratio of the longest to the shortest edge is within a given range. This problem is also interesting in the special case where all edges are required to be of unit length.

2 Figure 1 :

 21 Figure 1: (a) An outerplanar graph with its chain decomposition determined by edge e. The chain Ce is clockwise and it is in red; the children chains of Ce are in yellow and their children are in green. The short edges of Ce are dashed. (b) Same as (a) but with the opposite orientation for e; Ce is counterclockwise (the blue chain is a child of a green chain). To reduce the visual clutter, not all edges of G have been oriented. (c) Schematic drawing of Ce and of the next level of chains in the chain decomposition of (a); the chains of subsequent levels are not drawn.

Figure 2 :

 2 Figure 2: Illustration for the proof of Lemma 3.

Figure 3 :

 3 Figure 3: Example of graph G in the proof of Lemma 5 with k = 7.

Figure 4 :

 4 Figure 4: Illustration for the construction of Lemma 6.

2 and -a+b+c 2 ,Lemma 6 .

 226 and let d be the length of segment CD. Then, the following holds. Both triangles defined by D and, respectively, edges AC and BC have equal perimeter a+b+c 2

Figure 5 :

 5 Figure 5: For the proof of Theorem 2: (a) Embedding Gn of graph Gn. (b) Bounding from above the perimeters of some triangles in Gn.

Figure 5 (

 5 Figure 5(b). Then the perimeter of triangle (e 1 , v 1 ) is less than that of T 1 , which is less than the perimeter of T minus half the length of the shortest edge of T , by Lemma 6. But all edges of the Γ i have lengths at least 1 ρ * , so the perimeter of triangle (e 1 , v 1 ) is smaller than that of T minus 1 2ρ * . Now, if e is not the longest edge of T , then one of e 1 or e 2 must be. Let e denote this longest edge, then after the construction of G i+1 , e must be the longest edge of the (new) triangle T formed by e and v e because the edges of T are contained in T , and thus their lengths are at most the length of the longest edge of T , which is e . Thus, in the construction of G i+2 , one of the new triangles formed, by similar application of Lemma 6, has a perimeter that is at least 1 2ρ * shorter than the perimeter of T , which itself is shorter than the perimeter of T .In each of the two cases we have identified a triangle, either in G i+1 or in G i+2 , whose perimeter is shorter than that of T minus 1 2ρ * . Since the perimeter of T is at most 3, repeating this process 6ρ * times results in a triangle whose perimeter is negative, which is a contradiction and concludes the proof of Theorem 2.

Acknowledgments. The authors wish to thank David Eppstein for alerting us to some earlier related work.

dimensioni -Ricerca di Base 2018